POJ2044 Weather Forecast 题解

写了一个小时……不会……无耻地看题解去了……

关键在于存储状态的方式，真没想到……

每个状态要存当前坐标、天数和这个状态下四个角的情况，vis数组存整张图的访问情况，有天数、坐标、四个角的情况，只有这样才能保证唯一性。

还没见过这么毒瘤的状态记录题，我还是太 naive 了……

代码要多学习一个

#include <bits/stdc++.h>

using namespace std;

const int dx[9]={0,-1,-2,1,2,0,0,0,0};

const int dy[9]={0,0,0,0,0,-1,-2,1,2};

struct Node{int day,x,y,s[4];};

int n;

bool a[366][4][4],vis[366][4][4][7][7][7][7];

inline bool check(int x,int y,int day,int d[])

{

    if(x<0||y<0||x>2||y>2) return 0;

    for(int i=0;i<=1;++i)

        for(int j=0;j<=1;++j)

            if(a[day][x+i][y+j]) return 0;

    if(d[0]>=7||d[1]>=7||d[2]>=7||d[3]>=7) return 0;

    return 1;

}

bool bfs()

{

    if(a[1][1][1]||a[1][1][2]||a[1][2][1]||a[1][2][2]) return 0;

    queue<Node> q; memset(vis,0,sizeof(vis));

    int sd[4];

    q.push((Node){1,1,1,{1,1,1,1}});

    vis[1][1][1][1][1][1][1]=1;

    while(!q.empty())

    {

        Node now=q.front(); q.pop();

        if(now.day==n) return 1;

        for(int i=0;i<9;++i)

        {

            int x=now.x+dx[i],y=now.y+dy[i];

            for(int j=0;j<4;++j) sd[j]=now.s[j]+1;

            if(x==0&&y==0) sd[0]=0;

            if(x==0&&y==2) sd[1]=0;

            if(x==2&&y==0) sd[2]=0;

            if(x==2&&y==2) sd[3]=0;

            if(check(x,y,now.day+1,sd)&&\

            !vis[now.day+1][x][y][sd[0]][sd[1]][sd[2]][sd[3]])

            {

                q.push((Node){now.day+1,x,y,{sd[0],sd[1],sd[2],sd[3]}});

                vis[now.day+1][x][y][sd[0]][sd[1]][sd[2]][sd[3]]=1;

            }

        }

    }

    return 0;

}

int main()

{

    while(scanf("%d",&n)&&n)

    {

        for(int i=1;i<=n;++i)

            for(int j=0;j<4;++j)

                for(int k=0;k<4;++k)

                scanf("%d",&a[i][j][k]);

        printf("%d\n",bfs());

    }

    return 0;

}

巴特西

POJ2044 Weather Forecast 题解

最新文章

热门文章