[Devskill] DCP-60: Holloween Party

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DCP-60: Holloween Party
Source            : Devskill
Category          : Graph Theory
Algorithm         : 0-1 BFS
Verdict           : Accepted
#include <bits/stdc++.h>
 
using namespace std;
 
#define memo(a, b)           memset(a, b, sizeof(a))
 
void FAST() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
 
const int mx = 1010;
 
struct node
{
      int x, y;
      node (int x = 0, int y = 0)
      {
            x = x;
            y = y;
      }
};
 
int dr[] = {-1, +0, +1, +0};
int dc[] = {+0, +1, +0, -1};
 
int row, col;
 
int isInside(int r, int c)
{
      return (r>=0 && r<row && c>=0 && c<col);
}
 
char grid[mx][mx];
int dis[mx][mx];
int cost;
 
void bfs(int sX, int sY)
{
      memo(dis, 999999);
      deque <node> dq;
      dis[sX][sY] = 0;
      dq.push_front({sX, sY});
      while (!dq.empty()) 
      {
            node t = dq.front(); dq.pop_front();
            for (int f = 0; f < 4; f++) 
            {
                  int u = t.x + dr[f];
                  int v = t.y + dc[f];
                  if (!isInside(u, v)) continue;
                  bool flag = false;
                  if (grid[u][v] == grid[t.x][t.y])
                  {
                        cost = 0;
                        flag = true;
                  }
                  else
                  {
                        cost = 1;
                  }
                  if (dis[u][v] > dis[t.x][t.y] + cost)
                  {
                        dis[u][v] = dis[t.x][t.y] + cost;
                        if (flag) dq.push_front({u, v});
                        else dq.push_back({u, v});
                  }
            }
       }
}
 
int main()
{
      FAST();
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            cin >> row >> col;
            string str;
            for (int i = 0; i < row; i++)
            {
                  cin >> str;
                  for (int j = 0; j < str.size(); j++) grid[i][j] = str[j];
            }
            bfs(0, 0);
            cout << "Case " << tcase << ": "  << dis[row-1][col-1] << endl;
      }
      return 0;
}