1238 - Power Puff Girls - LOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
#define Case "Case "<<++kase<<": "
#define GRAY 0
#define WHITE 1
#define BLACK 2
#define imax INT_MAX
#define max3(a,b,c) max(a,max(b,c))
using namespace std;
string grid[21];
int xd[]={-1,0,1,0};
int yd[]={0,1,0,-1};
bool visited[21][21];
int dist[21][21];
int row , col;
int bfs(int i, int j){
    pair<int,int>p;
    queue<pair<int,int> >q;
    int mx = 0;
   for(int i=0; i<21; i++){
        for(int j=0; j<21; j++)dist[i][j]=imax;
    }
    p = {i,j};
    q.push(p);
    dist[i][j] = 0;
    visited[i][j] = true;
    while(!q.empty()){
        pair<int,int>pt;
        pt = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int x = pt.first;
            int y = pt.second;
            if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && grid[x+xd[i]][y+yd[i]] == 'h'){
                  dist[x+xd[i]][y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]);
                  mx = max(mx, dist[x+xd[i]][ y+yd[i]]);
                  return mx;
               
            }else{
                 if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && (grid[x+xd[i]][y+yd[i]] == '.' ||grid[x+xd[i]][y+yd[i]] == 'a'||grid[x+xd[i]][y+yd[i]] == 'b'||grid[x+xd[i]][y+yd[i]] == 'c' ) && !visited[x+xd[i]][y+yd[i]]){
                    dist[x+xd[i]][ y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]);
                    mx = max(mx, dist[x+xd[i]][ y+yd[i]]);
                    visited[x+xd[i]][y+yd[i]] = true;
                    q.push({x+xd[i],y+yd[i]});
                }
            }
        }
    }
    return mx;
}
int main()
{
   int T,kase=0;
   cin >> T;
   while(T--){
    cin >> row >> col;
    for(int i=0; i<row; i++){
        cin >> grid[i];
    }
    int a,b,c;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(grid[i][j] == 'a'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                a = bfs(i,j);
            }
            if(grid[i][j] == 'b'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                b = bfs(i,j);
            }
            if(grid[i][j] == 'c'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                c = bfs(i,j);
            }
        }
    }
        cout<<Case<<max3(a,b,c)<<newl;
   }
    return 0;
}