Advertisement
milon34

grid traversal by DFS

Jan 13th, 2023 (edited)
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. //problem link:   https://lightoj.com/problem/guilty-prince
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long int
  5. const int mx = 30;
  6. char grid[mx][mx];
  7. bool vis[mx][mx];
  8. int dx[] = {0, 0, 1, -1};
  9. int dy[] = {1, -1, 0, 0};
  10. int res = 0;
  11. int m, n;
  12. void dfs(int x, int y) {
  13.   vis[x][y] = true;
  14.   res++;
  15.   for (int i = 0; i < 4; i++) {
  16.     int x1 = x + dx[i];
  17.     int y1 = y + dy[i];
  18.     if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && !vis[x1][y1] &&
  19.         grid[x1][y1] != '#') {
  20.       dfs(x1, y1);
  21.     }
  22.   }
  23. }
  24. int main() {
  25.   ios_base::sync_with_stdio(false);
  26.   cin.tie(0);
  27.   cout.tie(0);
  28.   int tt, k = 1;
  29.   cin >> tt;
  30.   while (tt--) {
  31.     memset(vis, 0, sizeof(vis));
  32.     res = 0;
  33.     cin >> m >> n;
  34.     int x = 0, y = 0;
  35.     for (int i = 1; i <= n; i++) {
  36.       for (int j = 1; j <= m; j++) {
  37.         cin >> grid[i][j];
  38.         if (grid[i][j] == '@') {
  39.           x = i, y = j;
  40.         }
  41.       }
  42.     }
  43.     dfs(x, y);
  44.     cout << "Case " << k++ << ": " << res << "\n";
  45.   }
  46.   return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement