SRM550 Div2 Medium

550

やるだけ。シミュレーションする。

view plainprint?

1. const int H = 50 + 2;  
2. const int W = H;  
3.   
4. bool vis[H][W];  
5.   
6. const int di[] = {0, -1, 0, +1};  
7. const int dj[] = {+1, 0, -1, 0};  
8.   
9. bool f(int i, int j, int h, int w, vector<int> M)  
10. {  
11.   fill(&vis[0][0], &vis[H - 1][W], false);  
12.   int dir = 0;  
13.   int ni, nj;  
14.   
15.   for (int k = 0; k < M.size(); ++k) {  
16.     while (true) {  
17.       vis[i][j] = true;  
18.       ni = i + di[dir];  
19.       nj = j + dj[dir];  
20.       if (ni < 0 || nj < 0 || h <= ni || w <= nj || vis[ni][nj]) {  
21.         break;  
22.       } else {  
23.         --M[k];  
24.         i = ni;  
25.         j = nj;  
26.       }  
27.     }  
28.     dir = (dir + 1) % 4;  
29.     ni = i + di[dir];  
30.     nj = j + dj[dir];  
31.     if (ni < 0 || nj < 0 || h <= ni || w <= nj || vis[ni][nj]) {  
32.       return M[k] <= 0 && (k + 1) == M.size();  
33.     }  
34.     if (M[k]) {  
35.       return M[k] <= 0 && (k + 1) == M.size();  
36.     }  
37.   }  
38.   
39.   return true;  
40. }  
41.   
42. class RotatingBot {  
43. public:  
44.   int minArea(vector <int> moves)  
45.   {  
46.     const int inf = 1 << 30;  
47.     int mn = inf;  
48.   
49.     for (int h = 1; h < H; ++h) {  
50.       for (int w = 1; w < W; ++w) {  
51.         int j = w - moves[0] - 1;  
52.         if (j < 0) continue;  
53.         for (int i = 0; i < h; ++i) {  
54.           if (f(i, j, h, w, moves)) {  
55.             mn = min(mn, h * w);  
56.           }  
57.         }  
58.       }  
59.     }  
60.   
61.     return mn == inf ? -1 : mn;  
62.   }  
63. };  

const int H = 50 + 2;
const int W = H;

bool vis[H][W];

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

bool f(int i, int j, int h, int w, vector<int> M)
{
  fill(&vis[0][0], &vis[H - 1][W], false);
  int dir = 0;
  int ni, nj;

  for (int k = 0; k < M.size(); ++k) {
    while (true) {
      vis[i][j] = true;
      ni = i + di[dir];
      nj = j + dj[dir];
      if (ni < 0 || nj < 0 || h <= ni || w <= nj || vis[ni][nj]) {
        break;
      } else {
        --M[k];
        i = ni;
        j = nj;
      }
    }
    dir = (dir + 1) % 4;
    ni = i + di[dir];
    nj = j + dj[dir];
    if (ni < 0 || nj < 0 || h <= ni || w <= nj || vis[ni][nj]) {
      return M[k] <= 0 && (k + 1) == M.size();
    }
    if (M[k]) {
      return M[k] <= 0 && (k + 1) == M.size();
    }
  }

  return true;
}

class RotatingBot {
public:
  int minArea(vector <int> moves)
  {
    const int inf = 1 << 30;
    int mn = inf;

    for (int h = 1; h < H; ++h) {
      for (int w = 1; w < W; ++w) {
        int j = w - moves[0] - 1;
        if (j < 0) continue;
        for (int i = 0; i < h; ++i) {
          if (f(i, j, h, w, moves)) {
            mn = min(mn, h * w);
          }
        }
      }
    }

    return mn == inf ? -1 : mn;
  }
};