POJ 2458 DFS+判重

时间:2022-12-31 10:56:37

题意:

POJ 2458 DFS+判重

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);
}

POJ 2458 DFS+判重