暴搜一发，写个dp来剪枝

#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie();cout.tie();
typedef long long ll;
const int N = 1e1 + 7;
int n,m,t;
char m1[N][N],m2[N][N];
int dp[N][N][N],vis[N][N][N];
int sx=1,sy=1,sz=0,fx,fy,fz;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
void dfs(int x,int y,int z,int time){
	if(time>=dp[x][y][z]||vis[x][y][z]==1)return ;
	dp[x][y][z]=min(time,dp[x][y][z]);
	vis[x][y][z]=1;
	for(int i=0;i<4;i++){
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<1||xx>n||y<1||y>m)continue;
		if((z==0&&m1[xx][yy]=='*')||(z==1&&m2[xx][yy]=='*'))continue;
		if(z==0){
			if(m1[xx][yy]=='.'||m1[xx][yy]=='P')dfs(xx,yy,0,time+1);
			else if(m1[xx][yy]=='#'&&m2[xx][yy]!='*')dfs(xx,yy,1,time+1);
		}else{
			if(m2[xx][yy]=='.'||m2[xx][yy]=='P')dfs(xx,yy,1,time+1);
			else if(m2[xx][yy]=='#'&&m1[xx][yy]!='*')dfs(xx,yy,0,time+1);
		}
	}
	vis[x][y][z]=0;
}
int main() {
	ioio
	memset(dp,0x3f3f3f3f,sizeof dp);
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>m1[i][j];
			if(m1[i][j]=='P')
				fx=i,fy=j,fz=0;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>m2[i][j];
			if(m2[i][j]=='P')
				fx=i,fy=j,fz=1;
		}
	dfs(1,1,0,0);
	if(dp[fx][fy][fz]<=t)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}