UVa一道关于长方体的题。

不惜恋儿

//题目大意：给定6个矩形的长和宽w，h（1<=w，h<=10000)，判断它们能否构成长方体的6个面。
// UVa里的1587，uDebug全试了，都能过，结果还是Wrong Answer，想知道哪有问题，求大佬康康。

#include<stdio.h>
#include<string.h>

const int N = 10005;
int a[N][N];
int s[N];

int com(int a, int b, int c, int d)// 矩形ab与cd比较是否相同
{
        if(a == c && b == d) return 1;
        else if(a == d && b == c ) return 1;
        else return 0;
}

int main(){
        while(scanf("%d%d", &a[0][0], &a[0][1]) != EOF ){
        
            for(int i = 1; i < 6; i++)
                scanf("%d%d", &a[i][0], &a[i][1]);
            int max = a[0][0], min = a[0][0];
        
            for(int j = 0; j < 6; j++){
                for(int k = 0; k < 2; k ++){
                    if(max < a[j][k]) max = a[j][k];
                    if(min > a[j][k]) min = a[j][k];
                    s[a[j][k]]++;
                }
            }
            int p = 0, sum = 0, x = 0, y = 0, z = 0, t = 0;
            for(int i = min; i <= max; i++){
                if( s[i] && s[i] % 4 != 0) {    p = 1;break; }// 边数不是4的倍数
                if(s[i] && !t) {    x = i; t++; }// 长
                else if(s[i] && t == 1) {   y = i; t++; }// 宽
                else if(s[i] && t == 2){    z = i; t++; }// 高
            }
            if(p) { printf("IMPOSSIBLE\n");continue; }
            if(!z){
                if(s[x] > s[y]) z = x;
                else z = y;
            }// 长宽高只有两个数时
            int xy = 0, xz = 0, yz = 0;
            for(int i = 0; i < 6; i++){
                if(com(a[i][0], a[i][1], x, y)) xy ++;// 长宽
                else if(com(a[i][0], a[i][1], x, z)) xz ++; // 长高
                else if(com(a[i][0], a[i][1], z, y)) yz ++;// 宽高
            }
            if(xy % 2 != 0 || xz % 2 != 0 || yz % 2 != 0 || xy + xz + yz != 6) printf("IMPOSSIBLE\n");// 均应是2的倍数，且之和为6
            else printf("POSSIBLE\n");
            memset(a, 0, sizeof(a));
            memset(s, 0, sizeof(s));
        }
        return 0;
}

jackz007

#include <stdio.h>

// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？

int check(int d[6][2])
{
        int e[12] , f , i , j , k , m , * p , r                         ;
        for(p = d[0] , f = 1 , r = i = 0 ; i < 12 ; i ++) {
                if(p[i] > 0) {
                        e[i] = p[i]                                     ;
                } else {
                        f = 0                                           ;
                        break                                           ;
                }
        }
        if(f) {
                for(m = 12 , i = 0 ; i < m - 1 ; i ++) {
                        for(j = i + 1 ; j < m ; j ++) {
                                while(e[i] == e[j] && j < m) {
                                        for(k = j + 1 ; k < m ; k ++) {
                                                e[k - 1] = e[k]         ;
                                        }
                                        m --                            ;
                                }
                        }
                }
                if(m < 4) r = 1                                         ;
        }
        return r                                                        ;
}

int main(void)
{
        int d[6][2] = {0} , i                                           ;
        for(i = 0 ; i < 6; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])  ;
        if(check(d)) printf("Possible .\n")                             ;
        else printf("Impossible .\n")                                   ; 
}

        具体思路是，6 组 12 个数必须全都大于 0，在此基础上，删除重复的数据，如果最后剩下的数少于 4 个，那就必然是长方体的 6 个面无疑，否则，就一定不是。

不惜恋儿

jackz007 发表于 2021-1-17 20:24
具体思路是，6 组 12 个数必须全都大于 0，在此基础上，删除重复的数据，如果最后剩下的数少于 4 ...

这个想法很好，但是有情况需要在斟酌一下最后三个面一定能构成吗？

不惜恋儿

不惜恋儿 发表于 2021-1-17 20:45
这个想法很好，但是有情况需要在斟酌一下最后三个面一定能构成吗？

回贴还不太熟悉，暂时发不了图片给你看。你刚刚的代码需要完善。。我这有样例：

1 2
2 1
3 1
2 2
1 2
3 3
3 2
1 1
1 1
3 2
2 3
3 1
1 2
3 1
3 1
3 3
3 2
3 2
3 1
2 1
1 3
2 2
3 2
2 3
2 1
1 2
3 1
3 1
2 3
3 3
3 3
1 1
2 3
3 3
2 2
2 3
2 2
3 1
1 2
2 2
1 2
3 3
1 1
1 3
2 3
2 1
1 1
2 3
1 2
1 2
1 2
1 3
3 1
2 2
1 3
2 2
1 1
2 2
2 2
1 2
3 3
2 1
3 3
3 3
1 1
3 3
3 3
3 2
3 2
2 2
3 3
2 2
3 1
2 3
3 1
1 3
3 2
2 3
3 3
2 2
3 1
1 1
3 2
2 1
3 2
3 1
2 3
1 1
1 2
3 3
3 3
2 2
1 3
2 1
3 1
2 1
3 2
2 3
3 2
1 3
1 3
2 1
1 3
1 1
3 2
3 2
3 2
1 1
2 3
1 3
1 2
1 3
2 3
2 2
2 2
2 3
3 3
2 1
1 1
3 3

这些输出都是：

IMPOSSIBLE

jackz007

不惜恋儿 发表于 2021-1-17 20:48
回贴还不太熟悉，暂时发不了图片给你看。你刚刚的代码需要完善。。我这有样例：

这些输出都是：

          确实存在问题，再增加一个限制条件，筛出来的每个数在数组中都必须成对出现。

#include <stdio.h>

// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？

int check(int d[6][2])
{
        int c[3] = {0} , e[12] , f , i , j , k , m , * p , r            ;
        for(p = d[0] , f = 1 , r = i = 0 ; i < 12 ; i ++) {
                if(p[i] > 0) {
                        e[i] = p[i]                                     ;
                } else {
                        f = 0                                           ;
                        break                                           ;
                }
        }
        if(f) {
                for(m = 12 , i = 0 ; i < m - 1 ; i ++) {
                        for(j = i + 1 ; j < m ; j ++) {
                                while(e[i] == e[j] && j < m) {
                                        for(k = j + 1 ; k < m ; k ++) {
                                                e[k - 1] = e[k]         ;
                                        }
                                        m --                            ;
                                }
                        }
                }
                if(m < 4){
                        for(i = 0 ; i < 12 ; i ++) {
                                for(k = 0 ; k < m ; k ++) {
                                        if(p[i] == e[k]) c[k] ++        ;
                                }
                        }
                        for(k = 0 ; k < m ; k ++) if(c[k] % 2) break    ;
                        if(k == m) r = 1                                ;
                }
        }
        return r                                                        ;
}

int main(void)
{
        int d[6][2] = {0} , i                                           ;
        for(i = 0 ; i < 6; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])  ;
        if(check(d)) printf("Possible .\n")                             ;
        else printf("Impossible .\n")                                   ;
}

不惜恋儿

jackz007 发表于 2021-1-17 21:07
确实存在问题，再增加一个限制条件，筛出来的每个数在数组中都必须成对出现。

我刚刚给出的测试点你那都是IMPOSSIBLE吗? 我这有点不一样。

jackz007

不惜恋儿 发表于 2021-1-17 21:50
我刚刚给出的测试点你那都是IMPOSSIBLE吗? 我这有点不一样。

        举出一组有疑问的数据看看呢

不惜恋儿

jackz007 发表于 2021-1-17 21:07
确实存在问题，再增加一个限制条件，筛出来的每个数在数组中都必须成对出现。

每个数字都是2的倍数是可以的，但是如果像（1，1）（2，2）（3 ，3）||（1，1）（2，2）（1，1）也可以通过吗？

不惜恋儿

jackz007 发表于 2021-1-17 21:54
举出一组有疑问的数据看看呢

1 1
1 1
2 2
2 2
3 3
3 3

jackz007

不惜恋儿 发表于 2021-1-17 22:12

        你举的这些反例非常说明问题，我又把代码改了。
        现在的判定逻辑是：
        1、所有的数据必须大于 0；
        2、6 个面可以归结到 3 个以内不同的面，而且，每个面成对出现；
        3、经过简化，所有面的数据可以归结为 3 个以内不同的数值（长、宽、高）；
        

#include <stdio.h>

// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？

int check(int d[6][2])
{
        int c[3] = {0} , e[6][2] = {0} , f , i , j , k , m , * p , r            ;
        for(f = 1 , i = 0 ; i < 6; i ++) {
                if(d[i][0] > 0 && d[i][1] > 0) {
                        e[i][0] = d[i][0]                                       ;
                        e[i][1] = d[i][1]                                       ;
                } else {
                        f = 0                                                   ;
                        break                                                   ;
                }
        }
        if(f) {
                for(m = 6 , r = i = 0 ; i < m - 1 ; i ++) {
                        for(j = i + 1 ; j < m ; j ++) {
                                while(j < m && ((e[i][0] == e[j][0] && e[i][1] == e[j][1]) || (e[i][0] == e[j][1] && e[i][1] == e[j][0]))) {
                                        for(k = j + 1 ; k < m ; k ++) {
                                                e[k - 1][0] = e[k][0]           ;
                                                e[k - 1][1] = e[k][1]           ;        
                                        }
                                        m --                                    ;
                                }
                        }
                }        
                if(m < 4) {
                        for(i = 0 ; i < 6 ; i ++) {
                                for(k = 0 ; k < m ; k ++) {
                                        if((d[i][0] == e[k][0] && d[i][1] == e[k][1]) || (d[i][0] == e[k][1] && d[i][1] == e[k][0])) c[k] ++ ;
                                }        
                        }
                        for(i = 0 ; i < m ; i ++) if(c[i] % 2) break            ;
                        if(i == m) {
                                for(p = e[0] , m *= 2 , i = 0 ; i < m - 1 ; i ++) {
                                        for(j = i + 1 ; j < m ; j ++) {
                                                while(j < m && p[i] == p[j]) {
                                                        for(k = j + 1 ; k < m ; k ++) {
                                                                p[k - 1] = p[k] ;
                                                        }
                                                        m --                    ;
                                                }
                                        }
                                }
                                if(m < 4) r = 1                                 ;
                        }
                }
        }
        return r                                                                ;
}

int main(void)
{
        int d[6][2] = {0} , i                                           ;
        for(i = 0 ; i < 6 ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1]) ;
        if(check(d)) printf("Possible .\n")                             ;
        else printf("Impossible .\n")                                   ;
}

不惜恋儿

jackz007 发表于 2021-1-17 22:51
你举的这些反例非常说明问题，我又把代码改了。
        现在的判定逻辑是：
        1、所 ...

1 1
2 2
3 3
1 1
2 2
3 3
Possible .
你好，你的代码你有运行吗？我给你举的例子运行后还是可以构成。。。

jackz007

不惜恋儿 发表于 2021-1-18 13:09
1 1
2 2
3 3

        又改了，请你再测

#include <stdio.h>

// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？

int check(int d[6][2])
{
        int c[3] = {0} , e[6][2] = {0} , f , i , j , k , m , * p , r            ;
        for(f = 1 , i = 0 ; i < 6; i ++) {
                if(d[i][0] > 0 && d[i][1] > 0) {
                        e[i][0] = d[i][0]                                       ;
                        e[i][1] = d[i][1]                                       ;
                } else {
                        f = 0                                                   ;
                        break                                                   ;
                }
        }
        if(f) {
                for(m = 6 , r = i = 0 ; i < m - 1 ; i ++) {
                        for(j = i + 1 ; j < m ; j ++) {
                                while(j < m && ((e[i][0] == e[j][0] && e[i][1] == e[j][1]) || (e[i][0] == e[j][1] && e[i][1] == e[j][0]))) {
                                        for(k = j + 1 ; k < m ; k ++) {
                                                e[k - 1][0] = e[k][0]           ;
                                                e[k - 1][1] = e[k][1]           ;        
                                        }
                                        m --                                    ;
                                }
                        }
                }        
                if(m < 4) {
                        for(k = i = 0 ; i < m - 1 ; i ++) {
                                for(j = i + 1 ; j < m ; j ++) {
                                        if(e[i][0] == e[j][0] || e[i][1] == e[j][1] || e[i][1] == e[j][0] || e[i][0] == e[j][1]) k ++ ;
                                }
                        }
                        if(m == 1 || k == (m - 2) * 2 + 1) r = 1                ;
                }
        }
        return r                                                                                                                      ;
}

int main(void)
{
        int d[6][2] = {0} , i                                           ;
        for(i = 0 ; i < 6 ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1]) ;
        if(check(d)) printf("Possible .\n")                             ;
        else printf("Impossible .\n")                                   ;
}

不惜恋儿

jackz007 发表于 2021-1-18 14:01
又改了，请你再测

https://vjudge.net/problem/UVA-1587