POJ 1154 - LETTERS

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

概要

R 行 C 列のボードが与えられ，各マスには大文字のアルファベットが書いてある． 左上のマスからスタートし，今まで通ってきたマスと同じアルファベットの書かれているマスは通れないという制約で移動したとき，最長で何マス移動できるかを答える．

制約

• 1 <= R, C <= 20

解法

今まで通ってきたマスのアルファベットを状態としてもって BFS． が，なぜか昔の自分は stack を使っていた…

 1 #include <iostream>
 2 #include <vector>
 3 #include <set>
 4 #include <stack>
 5 using namespace std;
 6 
 7 struct state {
 8   int row, col, depth;
 9   bool visited[26];
10   state(int r, int c, int d, const bool* v)
11     : row(r), col(c), depth(d)
12   {
13     copy(v, v+26, visited);
14   }
15 };
16 
17 int main(void)
18 {
19   int R, C;
20   cin >> R >> C;
21 
22   vector<string> board(R);
23   for (int i = 0; i < R; i++) {
24     cin >> board[i];
25   }
26 
27   stack<state> stk;
28   bool v[26] = {false};
29   v[board[0][0]-'A'] = true;
30   stk.push(state(0, 0, 1, v));
31   int max_depth = 1;
32   while (!stk.empty()) {
33     state s = stk.top();
34     stk.pop();
35     max_depth = max(max_depth, s.depth);
36 
37     for (int d = 0; d < 4; d++) {
38       static const int dir_r[] = {-1, 0, 0, 1};
39       static const int dir_c[] = {0, 1, -1, 0};
40       const int r = s.row + dir_r[d];
41       const int c = s.col + dir_c[d];
42       if (0 <= r && r < R && 0 <= c && c < C && !s.visited[board[r][c]-'A']) {
43         s.visited[board[r][c]-'A'] = true;
44         stk.push(state(r, c, s.depth+1, s.visited));
45         s.visited[board[r][c]-'A'] = false;
46       }
47     }
48   }
49   cout << max_depth << endl;
50   return 0;
51 }