UVa一道关于长方体的题。

不惜恋儿

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

1. #include<stdio.h>
   
2. #include<string.h>
   
3. 
   
4. const int N = 10005;
   
5. int a[N][N];
   
6. int s[N];
   
7. 
   
8. int com(int a, int b, int c, int d)// 矩形ab与cd比较是否相同
   
9. {
   
10.         if(a == c && b == d) return 1;
    
11.         else if(a == d && b == c ) return 1;
    
12.         else return 0;
    
13. }
    
14. 
    
15. int main(){
    
16.         while(scanf("%d%d", &a[0][0], &a[0][1]) != EOF ){
    
17.         
    
18.             for(int i = 1; i < 6; i++)
    
19.                 scanf("%d%d", &a[i][0], &a[i][1]);
    
20.             int max = a[0][0], min = a[0][0];
    
21.         
    
22.             for(int j = 0; j < 6; j++){
    
23.                 for(int k = 0; k < 2; k ++){
    
24.                     if(max < a[j][k]) max = a[j][k];
    
25.                     if(min > a[j][k]) min = a[j][k];
    
26.                     s[a[j][k]]++;
    
27.                 }
    
28.             }
    
29.             int p = 0, sum = 0, x = 0, y = 0, z = 0, t = 0;
    
30.             for(int i = min; i <= max; i++){
    
31.                 if( s[i] && s[i] % 4 != 0) {    p = 1;break; }// 边数不是4的倍数
    
32.                 if(s[i] && !t) {    x = i; t++; }// 长
    
33.                 else if(s[i] && t == 1) {   y = i; t++; }// 宽
    
34.                 else if(s[i] && t == 2){    z = i; t++; }// 高
    
35.             }
    
36.             if(p) { printf("IMPOSSIBLE\n");continue; }
    
37.             if(!z){
    
38.                 if(s[x] > s[y]) z = x;
    
39.                 else z = y;
    
40.             }// 长宽高只有两个数时
    
41.             int xy = 0, xz = 0, yz = 0;
    
42.             for(int i = 0; i < 6; i++){
    
43.                 if(com(a[i][0], a[i][1], x, y)) xy ++;// 长宽
    
44.                 else if(com(a[i][0], a[i][1], x, z)) xz ++; // 长高
    
45.                 else if(com(a[i][0], a[i][1], z, y)) yz ++;// 宽高
    
46.             }
    
47.             if(xy % 2 != 0 || xz % 2 != 0 || yz % 2 != 0 || xy + xz + yz != 6) printf("IMPOSSIBLE\n");// 均应是2的倍数，且之和为6
    
48.             else printf("POSSIBLE\n");
    
49.             memset(a, 0, sizeof(a));
    
50.             memset(s, 0, sizeof(s));
    
51.         }
    
52.         return 0;
    
53. }

复制代码

jackz007

1. #include <stdio.h>
   
2. 
   
3. // 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
   
4. 
   
5. int check(int d[6][2])
   
6. {
   
7.         int e[12] , f , i , j , k , m , * p , r                         ;
   
8.         for(p = d[0] , f = 1 , r = i = 0 ; i < 12 ; i ++) {
   
9.                 if(p[i] > 0) {
   
10.                         e[i] = p[i]                                     ;
    
11.                 } else {
    
12.                         f = 0                                           ;
    
13.                         break                                           ;
    
14.                 }
    
15.         }
    
16.         if(f) {
    
17.                 for(m = 12 , i = 0 ; i < m - 1 ; i ++) {
    
18.                         for(j = i + 1 ; j < m ; j ++) {
    
19.                                 while(e[i] == e[j] && j < m) {
    
20.                                         for(k = j + 1 ; k < m ; k ++) {
    
21.                                                 e[k - 1] = e[k]         ;
    
22.                                         }
    
23.                                         m --                            ;
    
24.                                 }
    
25.                         }
    
26.                 }
    
27.                 if(m < 4) r = 1                                         ;
    
28.         }
    
29.         return r                                                        ;
    
30. }
    
31. 
    
32. int main(void)
    
33. {
    
34.         int d[6][2] = {0} , i                                           ;
    
35.         for(i = 0 ; i < 6; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])  ;
    
36.         if(check(d)) printf("Possible .\n")                             ;
    
37.         else printf("Impossible .\n")                                   ;
    
38. }

复制代码

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

不惜恋儿

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

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

不惜恋儿

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

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

1. 1 2
   
2. 2 1
   
3. 3 1
   
4. 2 2
   
5. 1 2
   
6. 3 3
   
7. 3 2
   
8. 1 1
   
9. 1 1
   
10. 3 2
    
11. 2 3
    
12. 3 1
    
13. 1 2
    
14. 3 1
    
15. 3 1
    
16. 3 3
    
17. 3 2
    
18. 3 2
    
19. 3 1
    
20. 2 1
    
21. 1 3
    
22. 2 2
    
23. 3 2
    
24. 2 3
    
25. 2 1
    
26. 1 2
    
27. 3 1
    
28. 3 1
    
29. 2 3
    
30. 3 3
    
31. 3 3
    
32. 1 1
    
33. 2 3
    
34. 3 3
    
35. 2 2
    
36. 2 3
    
37. 2 2
    
38. 3 1
    
39. 1 2
    
40. 2 2
    
41. 1 2
    
42. 3 3
    
43. 1 1
    
44. 1 3
    
45. 2 3
    
46. 2 1
    
47. 1 1
    
48. 2 3
    
49. 1 2
    
50. 1 2
    
51. 1 2
    
52. 1 3
    
53. 3 1
    
54. 2 2
    
55. 1 3
    
56. 2 2
    
57. 1 1
    
58. 2 2
    
59. 2 2
    
60. 1 2
    
61. 3 3
    
62. 2 1
    
63. 3 3
    
64. 3 3
    
65. 1 1
    
66. 3 3
    
67. 3 3
    
68. 3 2
    
69. 3 2
    
70. 2 2
    
71. 3 3
    
72. 2 2
    
73. 3 1
    
74. 2 3
    
75. 3 1
    
76. 1 3
    
77. 3 2
    
78. 2 3
    
79. 3 3
    
80. 2 2
    
81. 3 1
    
82. 1 1
    
83. 3 2
    
84. 2 1
    
85. 3 2
    
86. 3 1
    
87. 2 3
    
88. 1 1
    
89. 1 2
    
90. 3 3
    
91. 3 3
    
92. 2 2
    
93. 1 3
    
94. 2 1
    
95. 3 1
    
96. 2 1
    
97. 3 2
    
98. 2 3
    
99. 3 2
    
100. 1 3
     
101. 1 3
     
102. 2 1
     
103. 1 3
     
104. 1 1
     
105. 3 2
     
106. 3 2
     
107. 3 2
     
108. 1 1
     
109. 2 3
     
110. 1 3
     
111. 1 2
     
112. 1 3
     
113. 2 3
     
114. 2 2
     
115. 2 2
     
116. 2 3
     
117. 3 3
     
118. 2 1
     
119. 1 1
     
120. 3 3

复制代码

这些输出都是：

1. IMPOSSIBLE

复制代码

jackz007

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

这些输出都是：

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

1. #include <stdio.h>
   
2. 
   
3. // 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
   
4. 
   
5. int check(int d[6][2])
   
6. {
   
7.         int c[3] = {0} , e[12] , f , i , j , k , m , * p , r            ;
   
8.         for(p = d[0] , f = 1 , r = i = 0 ; i < 12 ; i ++) {
   
9.                 if(p[i] > 0) {
   
10.                         e[i] = p[i]                                     ;
    
11.                 } else {
    
12.                         f = 0                                           ;
    
13.                         break                                           ;
    
14.                 }
    
15.         }
    
16.         if(f) {
    
17.                 for(m = 12 , i = 0 ; i < m - 1 ; i ++) {
    
18.                         for(j = i + 1 ; j < m ; j ++) {
    
19.                                 while(e[i] == e[j] && j < m) {
    
20.                                         for(k = j + 1 ; k < m ; k ++) {
    
21.                                                 e[k - 1] = e[k]         ;
    
22.                                         }
    
23.                                         m --                            ;
    
24.                                 }
    
25.                         }
    
26.                 }
    
27.                 if(m < 4){
    
28.                         for(i = 0 ; i < 12 ; i ++) {
    
29.                                 for(k = 0 ; k < m ; k ++) {
    
30.                                         if(p[i] == e[k]) c[k] ++        ;
    
31.                                 }
    
32.                         }
    
33.                         for(k = 0 ; k < m ; k ++) if(c[k] % 2) break    ;
    
34.                         if(k == m) r = 1                                ;
    
35.                 }
    
36.         }
    
37.         return r                                                        ;
    
38. }
    
39. 
    
40. int main(void)
    
41. {
    
42.         int d[6][2] = {0} , i                                           ;
    
43.         for(i = 0 ; i < 6; i ++) scanf("%d%d" , & d[i][0] , & d[i][1])  ;
    
44.         if(check(d)) printf("Possible .\n")                             ;
    
45.         else printf("Impossible .\n")                                   ;
    
46. }

复制代码

不惜恋儿

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
   
2. 1 1
   
3. 2 2
   
4. 2 2
   
5. 3 3
   
6. 3 3

复制代码

jackz007

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

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

1. #include <stdio.h>
   
2. 
   
3. // 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
   
4. 
   
5. int check(int d[6][2])
   
6. {
   
7.         int c[3] = {0} , e[6][2] = {0} , f , i , j , k , m , * p , r            ;
   
8.         for(f = 1 , i = 0 ; i < 6; i ++) {
   
9.                 if(d[i][0] > 0 && d[i][1] > 0) {
   
10.                         e[i][0] = d[i][0]                                       ;
    
11.                         e[i][1] = d[i][1]                                       ;
    
12.                 } else {
    
13.                         f = 0                                                   ;
    
14.                         break                                                   ;
    
15.                 }
    
16.         }
    
17.         if(f) {
    
18.                 for(m = 6 , r = i = 0 ; i < m - 1 ; i ++) {
    
19.                         for(j = i + 1 ; j < m ; j ++) {
    
20.                                 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]))) {
    
21.                                         for(k = j + 1 ; k < m ; k ++) {
    
22.                                                 e[k - 1][0] = e[k][0]           ;
    
23.                                                 e[k - 1][1] = e[k][1]           ;        
    
24.                                         }
    
25.                                         m --                                    ;
    
26.                                 }
    
27.                         }
    
28.                 }        
    
29.                 if(m < 4) {
    
30.                         for(i = 0 ; i < 6 ; i ++) {
    
31.                                 for(k = 0 ; k < m ; k ++) {
    
32.                                         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] ++ ;
    
33.                                 }        
    
34.                         }
    
35.                         for(i = 0 ; i < m ; i ++) if(c[i] % 2) break            ;
    
36.                         if(i == m) {
    
37.                                 for(p = e[0] , m *= 2 , i = 0 ; i < m - 1 ; i ++) {
    
38.                                         for(j = i + 1 ; j < m ; j ++) {
    
39.                                                 while(j < m && p[i] == p[j]) {
    
40.                                                         for(k = j + 1 ; k < m ; k ++) {
    
41.                                                                 p[k - 1] = p[k] ;
    
42.                                                         }
    
43.                                                         m --                    ;
    
44.                                                 }
    
45.                                         }
    
46.                                 }
    
47.                                 if(m < 4) r = 1                                 ;
    
48.                         }
    
49.                 }
    
50.         }
    
51.         return r                                                                ;
    
52. }
    
53. 
    
54. int main(void)
    
55. {
    
56.         int d[6][2] = {0} , i                                           ;
    
57.         for(i = 0 ; i < 6 ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1]) ;
    
58.         if(check(d)) printf("Possible .\n")                             ;
    
59.         else printf("Impossible .\n")                                   ;
    
60. }

复制代码

不惜恋儿

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

        又改了，请你再测

1. #include <stdio.h>
   
2. 
   
3. // 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
   
4. 
   
5. int check(int d[6][2])
   
6. {
   
7.         int c[3] = {0} , e[6][2] = {0} , f , i , j , k , m , * p , r            ;
   
8.         for(f = 1 , i = 0 ; i < 6; i ++) {
   
9.                 if(d[i][0] > 0 && d[i][1] > 0) {
   
10.                         e[i][0] = d[i][0]                                       ;
    
11.                         e[i][1] = d[i][1]                                       ;
    
12.                 } else {
    
13.                         f = 0                                                   ;
    
14.                         break                                                   ;
    
15.                 }
    
16.         }
    
17.         if(f) {
    
18.                 for(m = 6 , r = i = 0 ; i < m - 1 ; i ++) {
    
19.                         for(j = i + 1 ; j < m ; j ++) {
    
20.                                 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]))) {
    
21.                                         for(k = j + 1 ; k < m ; k ++) {
    
22.                                                 e[k - 1][0] = e[k][0]           ;
    
23.                                                 e[k - 1][1] = e[k][1]           ;        
    
24.                                         }
    
25.                                         m --                                    ;
    
26.                                 }
    
27.                         }
    
28.                 }        
    
29.                 if(m < 4) {
    
30.                         for(k = i = 0 ; i < m - 1 ; i ++) {
    
31.                                 for(j = i + 1 ; j < m ; j ++) {
    
32.                                         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 ++ ;
    
33.                                 }
    
34.                         }
    
35.                         if(m == 1 || k == (m - 2) * 2 + 1) r = 1                ;
    
36.                 }
    
37.         }
    
38.         return r                                                                                                                      ;
    
39. }
    
40. 
    
41. int main(void)
    
42. {
    
43.         int d[6][2] = {0} , i                                           ;
    
44.         for(i = 0 ; i < 6 ; i ++) scanf("%d%d" , & d[i][0] , & d[i][1]) ;
    
45.         if(check(d)) printf("Possible .\n")                             ;
    
46.         else printf("Impossible .\n")                                   ;
    
47. }

复制代码

不惜恋儿

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

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

复制代码