爽死了 两个小时又切掉一题某人的fail!
递归大美!!! 我的思维和机器的思维真是惊人的合拍啊^^
思路:
把矩阵分成两个三角矩阵
-+-- - --- -- -- -+- -
这样然后先对上三角的第一行和下三角的(左起)第一列枚举,接着对上三角第二行和下三角第二列枚举,关键就是在从“一”进入“二”的时候 对左上角的矩形进行判断,这一个矩形是进入“二”以后再也接触不到的一个区域,如果此区域不是全部open那以后的递归就不用做了,大大提高效率 :) 自己想出来的噢~~ AC32ms 看了比绝大部分人快 也~~
debug用了大半个小时 其实只有一个错……上三角的最后一行没有进行枚举,无法得到结果,浪费那么长时间遗憾啊
debug的时候想到的技巧:因为递归层数太多显然无法一步一步调试 于是我加了这段判定代码:
if(r[0][0]&&!r[0][1]&&r[0][2]&&r[0][3] &&!r[1][0]&&!r[1][1]&&!r[1][2]&&!r[1][3] &&!r[2][0]&&!r[2][1]&&!r[2][2]&&!r[2][3] &&r[3][0]&&!r[3][1]&&r[3][2]) i=1;
在i=1;上面设breakpoint就可以一步到达终点来调试了..开始多加了个&&r[3][3]因为下面的bug一直搞不出来
擦 来不及了 赶快贴了代码去学校抄作业
#include <cstdio> bool a[4][4],r[4][4]; void change(int x,int y) { int i; for(i=0;i<4;i++) { a[x][i]=a[x][i]?false:true; a[i][y]=a[i][y]?false:true; } a[x][y]=a[x][y]?false:true; r[x][y]=r[x][y]?false:true; } bool calc(bool istop,int row,int from) { int i,j; /*TESTER for(i=0;i<4;i++) { for(j=0;j<4;j++) printf("%d",r[i][j]); printf("\n"); } if(r[0][0]&&!r[0][1]&&r[0][2]&&r[0][3] &&!r[1][0]&&!r[1][1]&&!r[1][2]&&!r[1][3] &&!r[2][0]&&!r[2][1]&&!r[2][2]&&!r[2][3] &&r[3][0]&&!r[3][1]&&r[3][2]) i=1;*/ if(!istop&&row==3) { for(i=0;i<4;i++) if((!a[i][3])||(!a[3][i])) return false; return true; } if(istop) { if(from>3-row) return calc(false,row,0); if(calc(true,row,from+1)) return true; change(row,from+row); if(calc(true,row,from+1)) return true; change(row,from+row); return false; } else { if(from>2-row) { for(i=0;i<=row;i++) if((!a[i][row])||(!a[row][i])) return false; return calc(true,row+1,0); } if(calc(false,row,from+1)) return true; change(row+from+1,row); if(calc(false,row,from+1)) return true; change(row+from+1,row); return false; } } int main() { int i,j,n; for(i=0;i<4;i++) { for(j=0;j<4;j++) a[i][j]=getchar()=='-'?true:false; getchar(); r[i][j]=false; } calc(true,0,0); n=0; for(i=0;i<4;i++) for(j=0;j<4;j++) if(r[i][j]) n++; printf("%d\n",n); for(i=0;i<4;i++) for(j=0;j<4;j++) if(r[i][j]) printf("%d %d\n",i+1,j+1); return 0; }