7.A计划

原题：https://www.acwing.com/problem/content/solution/4236/1/

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=15,INF=1e9;
int n,m,limit;
char g[2][N][N];
int dist[2][N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct Node{
    int x,y,z;
};

bool bfs()
{
    queue<Node> q;
    q.push({0,0,0});
    memset(dist,0x3f,sizeof dist);
    dist[0][0][0]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(g[t.z][t.x][t.y]=='P'){
            return dist[t.z][t.x][t.y]<=limit;
        }
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+t.x,y=dy[i]+t.y,z=t.z;
            if(x<0||x>=n||y<0||y>=m||g[z][x][y]=='*') continue;
            if(g[z][x][y]=='#'){
                if(g[z^1][x][y]=='#') continue;
                if(g[z^1][x][y]=='*') continue;
                if(dist[z^1][x][y]!=0x3f3f3f3f) continue;
                dist[z^1][x][y]=dist[t.z][t.x][t.y]+1;
                q.push({x,y,z^1});
            }
            else if(dist[z][x][y]==0x3f3f3f3f){
                dist[z][x][y]=dist[t.z][t.x][t.y]+1;
                q.push({x,y,z});
            }
        }
    }
    return false;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&limit);
        for(int i=0;i<2;i++)
            for(int j=0;j<n;j++)
                scanf("%s",g[i][j]);
        if(bfs()) puts("YES");
        else puts("NO");
    }
    return 0;
}