SRM588 Div2 Hard

1000

view plainprint?

1. const int H = 50 + 1;  
2. const int W = 50 + 1;  
3. const int L = (50 + 1) * 50;  
4. bool vis[H][W][L];  
5.   
6. char g[H][W];  
7. string M;  
8. int h, w;  
9. vector< pair<int, int> > A;  
10.   
11. const int di[] = {0, 0, -1, +1};  
12. const int dj[] = {-1, +1, 0, 0};  
13.   
14. bool rec(int bi, int bj, int len)  
15. {  
16.   if (vis[bi][bj][len]) return false;  
17.   
18.   int ai = A[len].first;  
19.   int aj = A[len].second;  
20.   if (ai == bi && aj == bj) {  
21.     return vis[bi][bj][len] = false;  
22.   }  
23.   
24.   if (len == M.size()) return true;  
25.   
26.   vis[bi][bj][len] = true;  
27.   
28.   for (int d = 0; d < 4; ++d) {  
29.     int ni = bi + di[d];  
30.     int nj = bj + dj[d];  
31.     if (ni < 0 || nj < 0) continue;  
32.     if (h <= ni || w <= nj) continue;  
33.     if (g[ni][nj] == '#') continue;  
34.     if (ni == ai && nj == aj) continue;  
35.     if (rec(ni, nj, len + 1)) return true;  
36.   }  
37.   
38.   return false;  
39. }  
40.   
41. class GameInDarknessDiv2 {  
42. public:  
43.   string check(vector <string> field, vector <string> moves)  
44.   {  
45.     h = field.size();  
46.     w = field[0].size();  
47.     for (int i = 0; i < h; ++i) {  
48.       for (int j = 0; j < w; ++j) {  
49.         g[i][j] = field[i][j];  
50.       }  
51.     }  
52.   
53.     M = accumulate(moves.begin(), moves.end(), string(""));  
54.   
55.     fill(&vis[0][0][0], &vis[H - 1][W - 1][L - 1] + 1, false);  
56.   
57.     int ai = 0, aj = 0;  
58.     int bi = 0, bj = 0;  
59.     for (int i = 0; i < h; ++i) {  
60.       for (int j = 0; j < w; ++j) {  
61.         if (g[i][j] == 'B') {  
62.           bi = i;  
63.           bj = j;  
64.         }  
65.         if (g[i][j] == 'A') {  
66.           ai = i;  
67.           aj = j;  
68.         }  
69.       }  
70.     }  
71.   
72.     A.clear();  
73.     for (int i = 0; i < M.size(); ++i) {  
74.       if (M[i] == 'U') --ai;  
75.       if (M[i] == 'D') ++ai;  
76.       if (M[i] == 'R') ++aj;  
77.       if (M[i] == 'L') --aj;  
78.       A.push_back(make_pair(ai, aj));  
79.     }  
80.   
81.     return rec(bi, bj, 0) ? "Bob wins" : "Alice wins";  
82.   }  

const int H = 50 + 1;
const int W = 50 + 1;
const int L = (50 + 1) * 50;
bool vis[H][W][L];

char g[H][W];
string M;
int h, w;
vector< pair<int, int> > A;

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

bool rec(int bi, int bj, int len)
{
  if (vis[bi][bj][len]) return false;

  int ai = A[len].first;
  int aj = A[len].second;
  if (ai == bi && aj == bj) {
    return vis[bi][bj][len] = false;
  }

  if (len == M.size()) return true;

  vis[bi][bj][len] = true;

  for (int d = 0; d < 4; ++d) {
    int ni = bi + di[d];
    int nj = bj + dj[d];
    if (ni < 0 || nj < 0) continue;
    if (h <= ni || w <= nj) continue;
    if (g[ni][nj] == '#') continue;
    if (ni == ai && nj == aj) continue;
    if (rec(ni, nj, len + 1)) return true;
  }

  return false;
}

class GameInDarknessDiv2 {
public:
  string check(vector <string> field, vector <string> moves)
  {
    h = field.size();
    w = field[0].size();
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        g[i][j] = field[i][j];
      }
    }

    M = accumulate(moves.begin(), moves.end(), string(""));

    fill(&vis[0][0][0], &vis[H - 1][W - 1][L - 1] + 1, false);

    int ai = 0, aj = 0;
    int bi = 0, bj = 0;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        if (g[i][j] == 'B') {
          bi = i;
          bj = j;
        }
        if (g[i][j] == 'A') {
          ai = i;
          aj = j;
        }
      }
    }

    A.clear();
    for (int i = 0; i < M.size(); ++i) {
      if (M[i] == 'U') --ai;
      if (M[i] == 'D') ++ai;
      if (M[i] == 'R') ++aj;
      if (M[i] == 'L') --aj;
      A.push_back(make_pair(ai, aj));
    }

    return rec(bi, bj, 0) ? "Bob wins" : "Alice wins";
  }