C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
bool arr[366][4][4];//存放命令行读取的数据
bool state[366][3][3][7][7][7][7];
//state 不同的先后顺序可能走出一样的局面，这样的局面不用再深搜，否则会超时
int dx[]={0,1,0,-1,0};
int dy[]={1,0,-1,0,0};
//可能的移动方向
int dfs(int n,int x,int y,int k,int s1,int s2,int s3,int s4){
    if(state[k][x][y][s1][s2][s3][s4])return false; 
    //如果已经搜过了，所表示一定是搜失败了，否则就结局了
    state[k][x][y][s1][s2][s3][s4]=true;
    //标记该状态已经被搜过
    if(arr[k][x][y]||arr[k][x+1][y]||arr[k][x][y+1]||arr[k][x+1][y+1])return false;
    //判断当前区域是否允许下雨，不允许该局面不合法
    int sa,sb,sc,sd;
    if(!x&&!y)sa=0;
    else sa=s1+1;
    if(x==2&&!y)sb=0;
    else sb=s2+1;
    if(!x&&y==2)sc=0;
    else sc=s3+1;
    if(x==2&&y==2)sd=0;
    else sd=s4+1;
    //四个角上如果下过雨则归0，否则在上一层的值上加一
    if(sa>=7||sb>=7||sc>=7||sd>=7)return false;
    //四个角上有超过7的值，则非法
    if(n==k)return true;
    //搜索到最后一层，并且四个角的值也不超过7，则是一个合法的结局。
    for(int i=0;i<5;i++){
        for(int g=1;g<=2;g++){
            if(x+dx[i]*g>=0&&x+dx[i]*g<3&&y+dy[i]*g>=0&&y+dy[i]*g<3){//判断是否可以移动
                if(dfs(n,x+dx[i]*g,y+dy[i]*g,k+1,sa,sb,sc,sd))return true;
            }
        }
    }
    return false;
}
int main(){
    int n;
    while(cin>>n,n){
        memset(state,0,sizeof state);
        for(int i=1;i<=n;i++){
            for(int j=0;j<4;j++){
                for(int k=0;k<4;k++){
                    cin>>arr[i][j][k];
                }
            }
        }
        cout<<dfs(n,1,1,1,0,0,0,0)<<endl;
    }
    return 0;

}