wasim

#include <bits/stdc++.h>
using namespace std;
const int mx=205;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int N,M,vis[mx][mx],dis[mx][mx];
int stx,sty,enx,eny,ans;
char grid[mx][mx];
bool is_valid(int x,int y,int con){
    if(con==1){
        if(x>=1 && y>=1 && x<=N && y<=M && (grid[x][y]=='.' && grid[x][y]!='*') && vis[x][y]==0){
            return true;
        }
        return false;
    }
}

int BFS(int sx,int sy,int ex,int ey,int con){
    clr();
    vis[sx][sy]=1;
    dis[sx][sy]=0;
    queue <PII> Q;
    Q.push({sx,sy});
    while(!Q.empty()){
        int u=Q.front().first;
        int v=Q.front().second;
        Q.pop();
        if(u==ex && v==ey){
            return dis[u][v];
        }
        for(int i=0; i<4; i++){
            int xx=u+dx[i];
            int yy=v+dy[i];
            if(con==1){
                if(is_valid(xx,yy,1)){
                    vis[xx][yy]=1;
                    dis[xx][yy]=dis[u][v]+1;
                    Q.push({xx,yy});
                }
            }else{
                if(is_valid(xx,yy,2)){

                }
            }
        }


    }
}

int main() {
    int T;
    scanf("%d",&t);
    int cnt=0;
    while(t--) {
        scanf("%d %d",&N,&M);
        getchar();
        for(int i=1; i<=N; i++){
            for(int j=1; j<=M; j++){
                scanf("%c",&grid[i][j]);
                if(grid[i][j]=='*')
                    cnt++;
                else if(grid[i][j]=='P'){
                    stx=i,sty=j;
                }else if(grid[i][j]=='D'){
                    enx=i,endy=j;
                }
            }
            getchar();
        }
        ans=0;
        if(cnt<=1){
            ans=BFS(stx,sty,enx,eny,1);
        }else{
            ans=BFS(stx,sty,enx,eny,1);
            minn=INT_MAX;
            p= BFS(stx,sty,enx,eny,2);
            minn=INT_MAX;
            q= BFS(enx,eny,stx,sty,2);
        }
            printf("%d\n",ans);
    }
    return 0;
}