74 solutions
-
-4
#include<bits/stdc++.h> using namespace std; int N; char g[25][25][3]; set<int> s; bool st[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(st[i][j][b]) return ; //出现过直接结束 st[i][j][b]=true; //标记已经出现过 if(g[i][j][0]=='M'||g[i][j][0]=='O') //可以加了一位 { int r=g[i][j][1]-'1',c=g[i][j][2]-'1',idx=r*3+c; // 行 列 扩展了要填的位置 int pre=(b/pow3[idx])%3; //当前的数字 if(pre==0) //当前位置上是空的 { int now=g[i][j][0]=='M'?1:2; //得到当前位置上的数字 b=(b%pow3[idx])+now*pow3[idx]+(b-b%pow3[idx+1]); // 前面的部分 更新的状态 后面的部分 if(test_win(b)) { s.insert(b); return ; } } } if(g[i-1][j][0]!='#') dfs(i-1,j,b); //上 if(g[i+1][j][0]!='#') dfs(i+1,j,b); //下 if(g[i][j-1][0]!='#') dfs(i,j-1,b); //左 if(g[i][j+1][0]!='#') dfs(i,j+1,b); //右 } int main() { pow3[0]=1; for(int i=1;i<=9;i++) pow3[i]=pow3[i-1]*3; //pow3[i]表示3的i次方 int n; cin>>n; int sx,sy; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>g[i][j][0]>>g[i][j][1]>>g[i][j][2]; //board表示(i,j)的格子状态 if(g[i][j][0]=='B') //位置 { sx=i,sy=j; } } } //return 0; dfs(sx,sy,0); //开始搜索 cout<<s.size(); //方案的数目 return 0; }
Information
- ID
- 838
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 2
- Tags
- # Submissions
- 371
- Accepted
- 104
- Uploaded By