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

}