|
| 1 | +packageAlgorithms.dfs; |
| 2 | + |
| 3 | +/* |
| 4 | + * 输入一个19*19的矩阵，只包含数字0、1、2，表示两人下五子棋的棋牌状态，1、2分别表示两人的棋子，0表示空格。 |
| 5 | + * 要求判断当前状态下是否有人获胜（横向、竖向或者斜线方向连成5个同色棋子）。题目说明输入样例保证每条线上至多 |
| 6 | + * 只有连续5个同色棋子，并且保证至多只有1人获胜。如果有人获胜，输出获胜者（1或2）加一个冒号， |
| 7 | + * 接着输出获胜的五连珠的第一个棋子的坐标，从上到下从左到右序号最小的为第一个，序号从1开始编号。如果无人获胜，输出no。 |
| 8 | + * */ |
| 9 | +publicclassFiveChessman { |
| 10 | +privatestaticclassCoordinate { |
| 11 | +intcol; |
| 12 | +introw; |
| 13 | + |
| 14 | +publicCoordinate (intcol,introw) { |
| 15 | +this.col =col; |
| 16 | +this.row =row; |
| 17 | + } |
| 18 | + } |
| 19 | + |
| 20 | +publicstaticclassVisit { |
| 21 | +booleanright; |
| 22 | +booleandown; |
| 23 | +booleanrightDown; |
| 24 | +booleanleftDown; |
| 25 | + |
| 26 | +publicVisit (booleanright,booleandown,booleanrightDown,booleanleftDown) { |
| 27 | +this.right =right; |
| 28 | +this.down =down; |
| 29 | +this.rightDown =rightDown; |
| 30 | +this.leftDown =leftDown; |
| 31 | + } |
| 32 | + } |
| 33 | + |
| 34 | +publicstaticvoidmain(String[]args) { |
| 35 | +int[][]input = { |
| 36 | + {1,0,0,0,1,0}, |
| 37 | + {0,1,0,1,0,2}, |
| 38 | + {0,0,1,0,2,0}, |
| 39 | + {0,1,0,2,0,0}, |
| 40 | + {0,0,2,0,1,0}, |
| 41 | + {0,2,0,0,0,0} |
| 42 | + }; |
| 43 | + |
| 44 | +Coordinateresult =findWin(input); |
| 45 | +if (result !=null) { |
| 46 | +System.out.println("" +result.row +" " +result.col); |
| 47 | + } |
| 48 | + |
| 49 | + } |
| 50 | + |
| 51 | +// in 代表棋盘 |
| 52 | +publicstaticCoordinatefindWin(int[][]in) { |
| 53 | +if (in ==null ||in.length ==0) { |
| 54 | +returnnull; |
| 55 | + } |
| 56 | + |
| 57 | +introw =in.length; |
| 58 | +intcol =in[0].length; |
| 59 | + |
| 60 | +Visit[][]visit =newVisit[row][col]; |
| 61 | + |
| 62 | +for (inti =0;i <row;i++) { |
| 63 | +for (intj =0;j <col;j++) { |
| 64 | +// try to get the result from 4 directions. |
| 65 | +for (intk =0;k <4;k++) { |
| 66 | +visit[i][j] =newVisit(false,false,false,false); |
| 67 | +Coordinateret =findWinHelp(in,j,i,in[i][j],k,visit,0); |
| 68 | +if (ret !=null) { |
| 69 | +returnret; |
| 70 | + } |
| 71 | + } |
| 72 | + } |
| 73 | + } |
| 74 | + |
| 75 | +returnnull; |
| 76 | + } |
| 77 | + |
| 78 | +// row, col 代表我们现在正在扫描的点的坐标 |
| 79 | +publicstaticCoordinatefindWinHelp(int[][]in,intcol,introw,intside,intdirection,Visit[][]visit,intnum) { |
| 80 | +// 扫描不可以超过范围 |
| 81 | +if (col >=in.length ||row >=in.length ||row <0 ||col <0) { |
| 82 | +returnnull; |
| 83 | + } |
| 84 | + |
| 85 | +// if it is 0, just return. |
| 86 | +if (in[row][col] ==0) { |
| 87 | +returnnull; |
| 88 | + } |
| 89 | + |
| 90 | +if (side !=in[row][col]) { |
| 91 | +returnnull; |
| 92 | + } |
| 93 | + |
| 94 | +// we get the result. |
| 95 | +if (num ==4) { |
| 96 | +returnnewCoordinate(col,row); |
| 97 | + } |
| 98 | + |
| 99 | +if (visit[row][col] ==null) { |
| 100 | +visit[row][col] =newVisit(false,false,false,false); |
| 101 | + } |
| 102 | + |
| 103 | +if (direction ==0) { |
| 104 | +if (visit[row][col].right) { |
| 105 | +returnnull; |
| 106 | + } |
| 107 | +visit[row][col].right =true; |
| 108 | + |
| 109 | +// right |
| 110 | +returnfindWinHelp(in,col +1,row,side,direction,visit,num +1); |
| 111 | + }elseif (direction ==1) { |
| 112 | +if (visit[row][col].down) { |
| 113 | +returnnull; |
| 114 | + } |
| 115 | + |
| 116 | +visit[row][col].down =true; |
| 117 | + |
| 118 | +// down |
| 119 | +returnfindWinHelp(in,col,row +1,side,direction,visit,num +1); |
| 120 | + }elseif (direction ==2) { |
| 121 | +if (visit[row][col].rightDown) { |
| 122 | +returnnull; |
| 123 | + } |
| 124 | + |
| 125 | + |
| 126 | +visit[row][col].rightDown =true; |
| 127 | + |
| 128 | +// right down |
| 129 | +returnfindWinHelp(in,col +1,row +1,side,direction,visit,num +1); |
| 130 | + }elseif (direction ==3) { |
| 131 | +if (visit[row][col].leftDown) { |
| 132 | +returnnull; |
| 133 | + } |
| 134 | + |
| 135 | +visit[row][col].leftDown =true; |
| 136 | + |
| 137 | +// left down |
| 138 | +returnfindWinHelp(in,col -1,row +1,side,direction,visit,num +1); |
| 139 | + } |
| 140 | + |
| 141 | +returnnull; |
| 142 | + } |
| 143 | +} |