POJ 2458 DFS+判重

题意：


思路：
搜+判重 嗯搞定 （听说有好多人用7个for写得….）

//By SiriusRen #include <bitset> #include <cstdio>0 using namespace std; bitset<134217728>bit; char s[17][17],vis[17][17],xx[]={1,-1,0,0},yy[]={0,0,1,-1}; int ans; bool check(int x,int y){for(int i=0;i<4;i++){int dx=x+xx[i],dy=y+yy[i];if(dx>=0&&dy>0&&dx<5&&dy<6&&vis[dx][dy])return 1;}return 0; } void dfs(int x,int y,int recj,int rech,int hash){bit[hash]=1;if(recj+rech==7){if(recj>=4)ans++;return;}vis[x][y]=1;for(int i=0;i<5;i++)for(int j=1;j<=5;j++)if(check(i,j)&&!bit[hash|(1<<(i*5+j))]&&!vis[i][j]){if(s[i][j]=='J')dfs(i,j,recj+1,rech,hash|(1<<(i*5+j)));else dfs(i,j,recj,rech+1,hash|(1<<(i*5+j)));}vis[x][y]=0; } int main(){for(int i=0;i<7;i++)for(int j=0;j<7;j++)vis[i][j]=1;for(int i=0;i<5;i++)scanf("%s",s[i]+1);for(int i=0;i<5;i++)for(int j=1;j<=5;j++)vis[i][j]=0;for(int i=0;i<5;i++)for(int j=1;j<=5;j++)if(s[i][j]=='J')dfs(i,j,1,0,1<<(i*5+j));else dfs(i,j,0,1,1<<(i*5+j));printf("%d\n",ans); }

转载于:https://www.cnblogs.com/SiriusRen/p/6532204.html

总结

以上是生活随笔为你收集整理的POJ 2458 DFS+判重的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。