poj2308连连看dfs嵌dfs/bfs

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>

using namespace std;

const int N=14;
int n,m,num[6];
int  a[N][N];
char c;
int flag;
int dirx[4]={0,1,0,-1},
    diry[4]={1,0,-1,0};
int vis[N][N];

struct Node{
    int x,y,dir,trun;
    Node(int x,int y,int dir,int trun):x(x),y(y),dir(dir),trun(trun){
    };
};

bool in(int x,int y){
    return x>=0&&x<n&&y>=0&&y<m;
}


bool cant(){
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!in(i+1,j+1)) continue;
            if(!a[i][j]||!a[i][j+1]) continue;
            if(a[i][j]&&a[i+1][j]&&a[i][j]==a[i+1][j+1]&&a[i+1][j]==a[i][j+1]&&num[a[i][j]]==2&&num[a[i+1][j]]==2) return true;
        // 正方形对角线同&&相关的两个颜色块数目就剩正方形里的两个 
        }    
    }

    return false;
}

void bfs(int x,int y,int color,int sam[42][2],int &samn){
    queue<Node> q;
    memset(vis,0,sizeof(vis));

    Node f(x,y,-1,0);
    q.push(f);
    vis[x][y]=1;

    while(!q.empty()){
        f=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int nx=f.x+dirx[i],
                ny=f.y+diry[i],
                ntrun=f.trun;
            if(!in(nx,ny)||vis[nx][ny]||(a[nx][ny]!=color&&a[nx][ny]!=0)) continue;
            //next不在范围内|| 已经访问过||(next颜色与现循环颜色块不符&&next不是空块） 
            if(f.dir!=i&&f.dir!=-1)  ntrun+=+1;
            //方向不同&&不是第一次 
            if(ntrun>2) continue;
            //转弯超 
            vis[nx][ny]=1;
            if(a[nx][ny]==color){
                sam[samn][0]=nx;
                sam[samn][1]=ny;
                samn++;
                continue;
            }
            //sam记录相同块坐标 
            q.push(Node(nx,ny,i,ntrun));
        }
    }
}


void dfs(int cnt){
    if(flag) return;

    if(cnt==0){
        flag=1;return;
    }

    if(cant()) return;//cant必须放这里 原来放在main里这个是不对的可能出现：
//A***                 
//*AB*
//*BA*
//***A 
//但这里要排除：只剩下：
//***
//AB*
//BA*这个发生在过程中    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(flag) return;

            if(!a[i][j]) continue;//空块下一个

            int sam[42][2];//记录相同块的坐标，转三个弯最多30 
            int samn=0,nowcolor=a[i][j];
            bfs(i,j,nowcolor,sam,samn);//第ij个，颜色，现在同色的个数 

            a[i][j]=0; 
            num[nowcolor]-=2;
            //与下方配合假设消掉 
            for(int k=0;k<samn;k++){
                int x=sam[k][0],
                    y=sam[k][1];

                a[x][y]=0;//假设消掉 

                dfs(cnt-2);//假设消掉 
                a[x][y]=nowcolor;//还原现场 
            }
            a[i][j]=nowcolor;//还原现场 
            num[nowcolor]+=2;

        }    
    }
}


int main(int argc, char** argv) {
    int cnt;
    while(scanf("%d%d",&n,&m)==2&&n+m){
        flag=0;//是否可以消光 
        cnt=0;//目前剩下的还要消的颜色块 
        memset(num,0,sizeof(num));//num记录每种块的数量包括空块 
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin>>c;
                if(c=='*') num[0]++,a[i][j]=0;//空块不要消 
                else if(c=='A') num[1]++,a[i][j]=1,cnt++;
                else if(c=='B') num[2]++,a[i][j]=2,cnt++;
                else if(c=='C') num[3]++,a[i][j]=3,cnt++;
                else if(c=='D') num[4]++,a[i][j]=4,cnt++;
            }    
        }


        if(num[1]&1||num[2]&1||num[3]&1||num[4]&1){//颜色块否单一定消不掉 
            printf("no\n"); continue; 
        }

        dfs(cnt);
        if(flag) printf("yes\n");
        else  printf("no\n");
    }
    return 0;
}