lavida 1052.cpp

#include <cstdio>
#include <queue>

using namespace std;

struct ele {
   int r, c, m;
   ele() {}
   ele(int _r, int _c, int _m) {
      r = _r, c = _c, m = _m;
   }
};

char str[103][103];
bool chk[103][103];

int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };

int main() {

   int t;
   scanf("%d", &t);

   while (t--) {

      int r, c;
      scanf("%d %d", &r, &c);

      for (int i = 0; i < r; i++)
         scanf("%s", str[i]);

      queue < ele > q;

      for (int i = 0; i < r; i++) {
         for (int j = 0; j < c; j++) {
            chk[i][j] = false;
            if (str[i][j] == 'S') {
               chk[i][j] = true;
               q.emplace(i, j, 0);
            }
         }
      }

      int ans = -1;

      while (!q.empty()) {

         ele f = q.front(); q.pop();

         if (str[f.r][f.c] == 'E') {
            ans = f.m;
            break;
         }

         for (int i = 0; i < 4; i++) {

            ele g = { f.r + dr[i], f.c + dc[i], f.m + 1 };

            if (g.r < 0 || g.r >= r || g.c < 0 || g.c >= c)continue;

            if (str[g.r][g.c] == '#')continue;

            if (chk[g.r][g.c])continue;

            chk[g.r][g.c] = true;

            q.emplace(g);

         }

      }

      printf("%d\n", ans);

   }

}