本文共 2407 字，大约阅读时间需要 8 分钟。
突破口：充分利用每一堵墙，有墙出现，其所在的行、列都加权1（除非遇到另一堵墙才停止），依次从权值由高到低开始建，每建一座，其所在的行、列都设置为N（no）（除非遇到墙才停止）。
代码如下：
#include #include #include using namespace std;char map[6][6]; //制作一张图struct wall //记录墙的位置{ int x,y;}w[17];int main(){ int n,flag; int i,j,k; int yes,no,num; while(~scanf("%d",&n)&&n) { flag=0;k=0; for(i=0;i<=16;i++) w[i].x=w[i].y=0; for(i=1;i<=n;i++) {getchar(); for(j=1;j<=n;j++) { scanf("%c",&map[i][j]); if(map[i][j]=='.') //如果为'.'，就将它改为‘0’，表示初始权值为0 map[i][j]='0'; else if(map[i][j]=='X') //遇到墙，记录墙的位置及个数 { flag++; w[k].x=i;w[k].y=j;k++; } } } if(flag==0) printf("%d\n",n); //没有墙的情况 else { if(n==1) printf("0\n"); //n==1还有n==2的情况很简单，讨论一下就好了 else if(n==2) { if(flag==1) printf("2\n"); else if(flag==2) { if(w[0].x!=w[1].x&&w[0].y!=w[1].y) //不同列不同行的才能两个 printf("2\n"); else printf("1\n"); } else if(flag==3) printf("1\n"); else printf("0\n"); } else //n==3或n==4的情况就比较复杂 { yes=no=num=0; for(i=0;i =1;j--) { if(map[ w[i].x ][j]!='X') map[w[i].x][j]++; else break; } for(j=w[i].x+1;j<=n;j++) { if(map[j][ w[i].y ]!='X') map[j][w[i].y]++; else break; } for(j=w[i].x-1;j>=1;j--) { if(map[j][ w[i].y ]!='X') map[j][w[i].y]++; else break; } } for(num=4;num>=0;num--) //num表权值，最大为4 { if(yes+no+flag==n*n) break; //图填满了就不用继续了 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if((map[i][j]-'0')==num) { map[i][j]='Y';yes++; for(k=j+1;k<=n;k++) //以‘Y’为定点，向其所在行、列赋值为‘N’ { if(isdigit(map[i][k])) { map[i][k]='N';no++; } else if(map[i][k]=='X') break; //遇到墙一定要停，下同 } for(k=j-1;k>=1;k--) { if(isdigit(map[i][k])) { map[i][k]='N';no++; } else if(map[i][k]=='X') break; } for(k=i+1;k<=n;k++) { if(isdigit(map[k][j])) { map[k][j]='N';no++; } else if(map[k][j]=='X') break; } for(k=i-1;k>=1;k--) { if(isdigit(map[k][j])) { map[k][j]='N';no++; } else if(map[k][j]=='X') break; } } } } } printf("%d\n",yes); } } } return 0;}
转载地址：http://qfdci.baihongyu.com/