hdu 2102 A计划

题意：略
思路：此题陷阱超多，当##，#*,*#时不能走进去，套下模板就行了。
#include <iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define N 20

struct node{

    int x,y,z;

    int step;

}pri;

int next[][2]={{1,0},{0,1},{-1,0},{0,-1}};

char map[2][N][N];

int n,m,time;

bool vis[2][N][N];

bool check(node a){

    if(a.x>=0&&a.x<n&&a.y>=0&&a.y<m&&map[a.z][a.x][a.y]!='*'

    &&!vis[a.z][a.x][a.y]&&a.step<=time)

        return 1;

    return 0;

}

bool bfs(){

    int i;

    queue<node>q;

    node tmp;

    memset(vis,0,sizeof(vis));

    q.push(pri);

    vis[pri.z][pri.x][pri.y]=1;

    while(!q.empty()){

        tmp=q.front();

        q.pop();

        if(map[tmp.z][tmp.x][tmp.y]=='P'&&tmp.step<=time)

            return 1;

        for(i=0;i<4;i++){

            node u;

            u=tmp;

            u.x+=next[i][0];

            u.y+=next[i][1];

            u.step+=1;

            if(check(u)){

                vis[u.z][u.x][u.y]=1;

                if(map[u.z][u.x][u.y]=='#'&&!vis[(u.z+1)%2][u.x][u.y]){

                    u.z=(u.z+1)%2;

                }

                q.push(u);

            }

        }

    }

    return 0;

}

int main(int argc, char** argv) {

    int t,i,j,k;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d",&n,&m,&time);

        for(k=0;k<2;k++)

        for(i=0;i<n;i++){

            scanf("%s",map[k][i]);

            for(j=0;j<m;j++){

                if(map[k][i][j]=='S'){

                    pri.x=i;

                    pri.y=j;

                    pri.z=k;

                    pri.step=0;

                }

            }

        }

        for(i=0;i<n;i++)

            for(j=0;j<m;j++){

                if(map[0][i][j]=='#'&&map[1][i][j]=='#')

                    map[0][i][j]=map[1][i][j]='*';

                if(map[0][i][j]=='*'&&map[1][i][j]=='#')

                    map[0][i][j]=map[1][i][j]='*';

                if(map[1][i][j]=='*'&&map[0][i][j]=='#')

                    map[0][i][j]=map[1][i][j]='*';

            }

        if(bfs())

            printf("YES\n");

        else

            printf("NO\n");

    }

    return 0;

}
巴特西

hdu 2102 A计划_bfs搜索

最新文章

热门文章
