POJ 3083 - Children of the Candy Corn

http://poj.org/problem?id=3083

概要

w * h の迷路とそのスタート地点・ゴール地点が与えられる． いわゆる右手法，左手法で進んだときのそれぞれのステップ数と，最短経路で進んだときのステップ数を答える．

制約

解法

最短経路は BFS するだけ． 右手法，左手法については向きという状態を持ちつつ1歩ずつ進むように実装した．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 static const int UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;
 7 static const int di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};
 8 
 9 int hand(const vector<string>& maze, const pair<int,int>& p, int d, int which)
10 {
11   int i = p.first, j = p.second;
12   for (int c = 2; ; c++) {
13     static const int a[] = {0, -1, 0, 1}, b[] = {-1, 0, 1, 0};
14     i += di[d];
15     j += dj[d];
16     if (maze[i][j] == 'E') {
17       return c;
18     }
19     if (maze[i+which*a[d]][j+which*b[d]] != '#') {
20       d = (d - which + 4) % 4;
21     } else if (maze[i+di[d]][j+dj[d]] != '#') {
22       // do nothing
23     } else if (maze[i-which*a[d]][j-which*b[d]] != '#') {
24       d = (d + which + 4) % 4;
25     } else {
26       d = (d + 2) % 4;
27     }
28   }
29 }
30 
31 int bfs(const vector<string>& maze, const pair<int,int>& start)
32 {
33   const int H = maze.size();
34   const int W = maze[0].size();
35   vector<vector<int> > dist(H, vector<int>(W, 1000000));
36   dist[start.first][start.second] = 1;
37   queue<pair<int,int> > q;
38   q.push(start);
39   while (!q.empty()) {
40     const int i = q.front().first;
41     const int j = q.front().second;
42     q.pop();
43     if (maze[i][j] == 'E') {
44       return dist[i][j];
45     }
46     for (int d = 0; d < 4; d++) {
47       const int k = i + di[d];
48       const int l = j + dj[d];
49       if (0 <= k && k < H && 0 <= l && l < W && maze[k][l] != '#' && dist[i][j]+1 < dist[k][l]) {
50         dist[k][l] = dist[i][j]+1;
51         q.push(make_pair(k, l));
52       }
53     }
54   }
55   return -1;
56 }
57 
58 
59 int main()
60 {
61   int T;
62   cin >> T;
63   while (T-- > 0) {
64     int H, W;
65     cin >> W >> H;
66     vector<string> maze(H);
67     pair<int,int> start;
68     for (int i = 0; i < H; i++) {
69       cin >> maze[i];
70       for (int j = 0; j < W; j++) {
71         if (maze[i][j] == 'S') {
72           start = make_pair(i, j);
73         }
74       }
75     }
76     int dir;
77     if (start.first == 0) {
78       dir = DOWN;
79     } else if (start.first == H-1) {
80       dir = UP;
81     } else if (start.second == 0) {
82       dir = RIGHT;
83     } else {
84       dir = LEFT;
85     }
86     cout << hand(maze, start, dir, 1) << ' ' << hand(maze, start, dir, -1) << ' ' << bfs(maze, start) << endl;
87   }
88   return 0;
89 }
poj/3083.cc