SRM440 Div2 Medium

500

パスをたどればいい

const int H = 50 + 1;
const int W = 50 + 1;
pair<int, int> path[H][W];

class MazeWanderingEasy {
public:
  int decisions(vector <string> maze)
  {
    const int h = maze.size();
    const int w = maze[0].size();

    pair<int, int> start, goal;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        if (maze[i][j] == 'M') start = make_pair(i, j);
        if (maze[i][j] == '*') goal = make_pair(i, j);
      }
    }

    fill(&path[0][0], &path[H][0], make_pair(-1, -1));

    bool vis[H][W];
    fill(&vis[0][0], &vis[H][0], false);
    vis[start.first][start.second] = true;

    const int di[] = {0, 0, -1, +1};
    const int dj[] = {-1, +1, 0, 0};

    queue< pair<int, int> > q;
    for (q.push(start); q.size() && !vis[goal.first][goal.second]; q.pop()) {
      pair<int, int> curr = q.front();
      for (int d = 0; d < 4; ++d) {
        int ni = curr.first + di[d];
        int nj = curr.second + dj[d];
        if (ni < 0 || nj < 0) continue;
        if (h <= ni || w <= nj) continue;
        if (vis[ni][nj]) continue;
        if (maze[ni][nj] == 'X') continue;
        vis[ni][nj] = true;
        path[ni][nj] = curr;
        q.push(make_pair(ni, nj));
      }
    }

    int ret = 0;
    pair<int, int> p = goal;
    while (true) {
      if (p != goal) {
        ret += (bool)(count(&path[0][0], &path[H][0], p) - 1);
      }
      if (p == start) break;
      p = path[p.first][p.second];
    }

    return ret;
  }
};