SRM440 Div2 Medium

500

パスをたどればいい

view plainprint?

1. const int H = 50 + 1;  
2. const int W = 50 + 1;  
3. pair<int, int> path[H][W];  
4.   
5. class MazeWanderingEasy {  
6. public:  
7.   int decisions(vector <string> maze)  
8.   {  
9.     const int h = maze.size();  
10.     const int w = maze[0].size();  
11.   
12.     pair<int, int> start, goal;  
13.     for (int i = 0; i < h; ++i) {  
14.       for (int j = 0; j < w; ++j) {  
15.         if (maze[i][j] == 'M') start = make_pair(i, j);  
16.         if (maze[i][j] == '*') goal = make_pair(i, j);  
17.       }  
18.     }  
19.   
20.     fill(&path[0][0], &path[H][0], make_pair(-1, -1));  
21.   
22.     bool vis[H][W];  
23.     fill(&vis[0][0], &vis[H][0], false);  
24.     vis[start.first][start.second] = true;  
25.   
26.     const int di[] = {0, 0, -1, +1};  
27.     const int dj[] = {-1, +1, 0, 0};  
28.   
29.     queue< pair<int, int> > q;  
30.     for (q.push(start); q.size() && !vis[goal.first][goal.second]; q.pop()) {  
31.       pair<int, int> curr = q.front();  
32.       for (int d = 0; d < 4; ++d) {  
33.         int ni = curr.first + di[d];  
34.         int nj = curr.second + dj[d];  
35.         if (ni < 0 || nj < 0) continue;  
36.         if (h <= ni || w <= nj) continue;  
37.         if (vis[ni][nj]) continue;  
38.         if (maze[ni][nj] == 'X') continue;  
39.         vis[ni][nj] = true;  
40.         path[ni][nj] = curr;  
41.         q.push(make_pair(ni, nj));  
42.       }  
43.     }  
44.   
45.     int ret = 0;  
46.     pair<int, int> p = goal;  
47.     while (true) {  
48.       if (p != goal) {  
49.         ret += (bool)(count(&path[0][0], &path[H][0], p) - 1);  
50.       }  
51.       if (p == start) break;  
52.       p = path[p.first][p.second];  
53.     }  
54.   
55.     return ret;  
56.   }  
57. };  

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;
  }
};