74 solutions
-
-2
#include<bits/stdc++.h> using namespace std; int N; char board[25][25][3]; set<int> s; bool beenthere[25][25][19683]; int pow3[10]; bool test_win(int b) { int cells[3][3]; //得到当前b表示的这个格子 for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { cells[i][j]=b%3; b/=3; } } for(int r=0;r<3;r++) //判断行是否满足MOO或OMM { if(cells[r][0]==1&&cells[r][1]==2&&cells[r][2]==2) return true; if(cells[r][0]==2&&cells[r][1]==2&&cells[r][2]==1) return true; } for(int c=0;c<3;c++)//判断列是否满足MOO或OMM { if(cells[0][c]==1&&cells[1][c]==2&&cells[2][c]==2) return true; if(cells[0][c]==2&&cells[1][c]==2&&cells[2][c]==1) return true; } //判断对角线是否满足MOO或OMM if(cells[0][0]==1&&cells[1][1]==2&&cells[2][2]==2) return true; if(cells[0][0]==2&&cells[1][1]==2&&cells[2][2]==1) return true; if(cells[2][0]==1&&cells[1][1]==2&&cells[0][2]==2) return true; if(cells[2][0]==2&&cells[1][1]==2&&cells[0][2]==1) return true; return false; } void dfs(int i,int j,int b) //走到了(i,j这个位置,当前状态是b) { if(beenthere[i][j][b]) return ; //出现过直接结束 beenthere[i][j][b]=true; //标记已经出现过 if(test_win(b)) { s.insert(b); return ; } if(board[i][j][0]=='M'||board[i][j][0]=='O') //可以加了一位 { int r=board[i][j][1]-'1',c=board[i][j][2]-'1',idx=r*3+c; // 行 列 扩展了要填的位置 int current_char=(b/pow3[idx])%3; //当前的数字 if(current_char==0) //当前位置上是空的 { int new_char=board[i][j][0]=='M'?1:2; //得到当前位置上的数字 b=(b%pow3[idx])+new_char*pow3[idx]+(b-b%pow3[idx+1]); // 前面的部分 更新的状态 后面的部分 } } if(board[i-1][j][0]!='#') dfs(i-1,j,b); //上 if(board[i+1][j][0]!='#') dfs(i+1,j,b); //下 if(board[i][j-1][0]!='#') dfs(i,j-1,b); //左 if(board[i][j+1][0]!='#') dfs(i,j+1,b); //右 } int main() { int bess_i,bess_j,bstate=0; pow3[0]=1; for(int i=1;i<=9;i++) pow3[i]=pow3[i-1]*3; //pow3[i]表示3的i次方 cin>>N; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { cin>>board[i][j][0]>>board[i][j][1]>>board[i][j][2]; //board表示(i,j)的格子状态 if(board[i][j][0]=='B') //位置 { bess_i=i,bess_j=j; } } } //return 0; dfs(bess_i,bess_j,bstate); //开始搜索 cout<<s.size(); //方案的数目 return 0; }
Information
- ID
- 838
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 2
- Tags
- # Submissions
- 371
- Accepted
- 104
- Uploaded By