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;
int s;
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, &a) != EOF ){
for(int i = 1; i < 6; i++)
scanf("%d%d", &a, &a);
int max = a, min = a;
for(int j = 0; j < 6; j++){
for(int k = 0; k < 2; k ++){
if(max < a) max = a;
if(min > a) min = a;
s]++;
}
}
int p = 0, sum = 0, x = 0, y = 0, z = 0, t = 0;
for(int i = min; i <= max; i++){
if( s && s % 4 != 0) { p = 1;break; }// 边数不是4的倍数
if(s && !t) { x = i; t++; }// 长
else if(s && t == 1) { y = i; t++; }// 宽
else if(s && t == 2){ z = i; t++; }// 高
}
if(p) { printf("IMPOSSIBLE\n");continue; }
if(!z){
if(s > s) z = x;
else z = y;
}// 长宽高只有两个数时
int xy = 0, xz = 0, yz = 0;
for(int i = 0; i < 6; i++){
if(com(a, a, x, y)) xy ++;// 长宽
else if(com(a, a, x, z)) xz ++; // 长高
else if(com(a, a, 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 于 2021-1-17 20:30 编辑
#include <stdio.h>
// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
int check(int d)
{
int e , f , i , j , k , m , * p , r ;
for(p = d , f = 1 , r = i = 0 ; i < 12 ; i ++) {
if(p > 0) {
e = p ;
} else {
f = 0 ;
break ;
}
}
if(f) {
for(m = 12 , i = 0 ; i < m - 1 ; i ++) {
for(j = i + 1 ; j < m ; j ++) {
while(e == e && j < m) {
for(k = j + 1 ; k < m ; k ++) {
e = e ;
}
m -- ;
}
}
}
if(m < 4) r = 1 ;
}
return r ;
}
int main(void)
{
int d = {0} , i ;
for(i = 0 ; i < 6; i ++) scanf("%d%d" , & d , & d);
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 不惜恋儿 发表于 2021-1-17 20:48
回贴还不太熟悉，暂时发不了图片给你看。你刚刚的代码需要完善。。我这有样例：
这些输出都是：
确实存在问题，再增加一个限制条件，筛出来的每个数在数组中都必须成对出现。
#include <stdio.h>
// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
int check(int d)
{
int c = {0} , e , f , i , j , k , m , * p , r ;
for(p = d , f = 1 , r = i = 0 ; i < 12 ; i ++) {
if(p > 0) {
e = p ;
} else {
f = 0 ;
break ;
}
}
if(f) {
for(m = 12 , i = 0 ; i < m - 1 ; i ++) {
for(j = i + 1 ; j < m ; j ++) {
while(e == e && j < m) {
for(k = j + 1 ; k < m ; k ++) {
e = e ;
}
m -- ;
}
}
}
if(m < 4){
for(i = 0 ; i < 12 ; i ++) {
for(k = 0 ; k < m ; k ++) {
if(p == e) c ++ ;
}
}
for(k = 0 ; k < m ; k ++) if(c % 2) break ;
if(k == m) r = 1 ;
}
}
return r ;
}
int main(void)
{
int d = {0} , i ;
for(i = 0 ; i < 6; i ++) scanf("%d%d" , & d , & d);
if(check(d)) printf("Possible .\n") ;
else printf("Impossible .\n") ;
} jackz007 发表于 2021-1-17 21:07
确实存在问题，再增加一个限制条件，筛出来的每个数在数组中都必须成对出现。
我刚刚给出的测试点你那都是IMPOSSIBLE吗? 我这有点不一样。 不惜恋儿 发表于 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-18 00:39 编辑
不惜恋儿 发表于 2021-1-17 22:12
你举的这些反例非常说明问题，我又把代码改了。
现在的判定逻辑是：
1、所有的数据必须大于 0；
2、6 个面可以归结到 3 个以内不同的面，而且，每个面成对出现；
3、经过简化，所有面的数据可以归结为 3 个以内不同的数值（长、宽、高）；
#include <stdio.h>
// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
int check(int d)
{
int c = {0} , e = {0} , f , i , j , k , m , * p , r ;
for(f = 1 , i = 0 ; i < 6; i ++) {
if(d > 0 && d > 0) {
e = d ;
e = d ;
} 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 == e && e == e) || (e == e && e == e))) {
for(k = j + 1 ; k < m ; k ++) {
e = e ;
e = e ;
}
m -- ;
}
}
}
if(m < 4) {
for(i = 0 ; i < 6 ; i ++) {
for(k = 0 ; k < m ; k ++) {
if((d == e && d == e) || (d == e && d == e)) c ++ ;
}
}
for(i = 0 ; i < m ; i ++) if(c % 2) break ;
if(i == m) {
for(p = e , m *= 2 , i = 0 ; i < m - 1 ; i ++) {
for(j = i + 1 ; j < m ; j ++) {
while(j < m && p == p) {
for(k = j + 1 ; k < m ; k ++) {
p = p ;
}
m -- ;
}
}
}
if(m < 4) r = 1 ;
}
}
}
return r ;
}
int main(void)
{
int d = {0} , i ;
for(i = 0 ; i < 6 ; i ++) scanf("%d%d" , & d , & d) ;
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 .
你好，你的代码你有运行吗？我给你举的例子运行后还是可以构成。。。 不惜恋儿 发表于 2021-1-18 13:09
1 1
2 2
3 3
又改了，请你再测
#include <stdio.h>
// 给出 6 组长宽数据，判断是否可能构成长方体的 6 个面？
int check(int d)
{
int c = {0} , e = {0} , f , i , j , k , m , * p , r ;
for(f = 1 , i = 0 ; i < 6; i ++) {
if(d > 0 && d > 0) {
e = d ;
e = d ;
} 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 == e && e == e) || (e == e && e == e))) {
for(k = j + 1 ; k < m ; k ++) {
e = e ;
e = e ;
}
m -- ;
}
}
}
if(m < 4) {
for(k = i = 0 ; i < m - 1 ; i ++) {
for(j = i + 1 ; j < m ; j ++) {
if(e == e || e == e || e == e || e == e) k ++ ;
}
}
if(m == 1 || k == (m - 2) * 2 + 1) r = 1 ;
}
}
return r ;
}
int main(void)
{
int d = {0} , i ;
for(i = 0 ; i < 6 ; i ++) scanf("%d%d" , & d , & d) ;
if(check(d)) printf("Possible .\n") ;
else printf("Impossible .\n") ;
} jackz007 发表于 2021-1-18 14:01
又改了，请你再测
https://vjudge.net/problem/UVA-1587
页:
[1]