1243 - Weather Forecast

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1243

問題

4×4で表される国がある。
風の神であるあなたは、2×2で表される雨雲を動かすことができる。
入力として、期間の長さと、それぞれの日のそれぞれの区画で市場もしくは祭りが開かれるかどうかの情報が与えられる。
市場もしくは祭りがあるときは雨が降ってほしくない。また、7日間連続で雨がふらないというのも許されない。
この条件を満たすような雨雲の動かし方があるかどうかを示せ。
ただし、雨雲は対角上に動かすことはできない。（停滞か東西南北のみ）
雨雲は日の初めに動かすものとし、市場・祭りの予定にかかわらず1日目は(1,1)(1,2)(2,1)(2,2)に存在する。

解法

DFS。
四隅が7日間連続で雨が降っていないことがなければ、他の区画で7日間連続で雨が降っていないことはないので、四隅で何日雨が降っていないかの情報を持てばいい。
状態数は、日にち(365)、雨雲の左上座標(3*3)、四隅の情報(7^4)を掛け合わしたもの。間に合いそう。
初期状態は、日にち0、雨雲の位置(1,1)、四隅はそれぞれ1日雨が降っていないという状態。
四隅の情報は、
S = [左上] + 7*[左下] + 7*7*[右上] + 7*7*7*[右下]
といった感じで持つ。
ある場所で6日雨が降っていないとき、次の日もそこに雨が降らない移動はしないようにする。

諸々の判定の位置や初期条件で結構ハマった。

ソース

int n;
int ba[365][4][4];
bool visited[365][3][3][7*7*7*7];

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

int hogex[] = {0, 0, 2, 2};
int hogey[] = {0, 2, 0, 2};

bool solve(int day, int y, int x, int S) {
  if (visited[day][y][x][S]) return 0;
  visited[day][y][x][S] = 1;
  
  REP(i, 2) 
    REP(j, 2)
      if (ba[day][y+i][x+j]) return 0;

  if (day == n-1) return 1;

  // 四隅の情報計算
  int tmp = S;
  int norain[4];
  REP(i,4) {
    norain[i] = tmp%7;
    tmp /= 7;
  }
  // 次の日へ
  REP(i, 4) {
    int xx = x, yy = y;
    if (i) {
      xx+=dx[i]; yy+=dy[i];
    }
    while(0<=xx&&xx<=2&&0<=yy&&yy<=2) {
      int nextS = 0;
      int tmp = 1;
      bool f = 0;
      REP(j, 4) {
        if (!(xx==hogex[j] && yy==hogey[j])) {
          if (norain[j] == 6) f = 1;
          nextS += tmp * (norain[j] + 1);
        }
        tmp *= 7;
      }
      if (!f && solve(day+1, yy, xx, nextS))
        return 1;
      yy += dy[i];
      xx += dx[i];
    }
  }
  return 0;
}

int main() {
  while(cin>>n,n) {
    REP(i, n) REP(j,4) REP(k,4) 
      cin >> ba[i][j][k];
    memset(visited,0,sizeof(visited));
    cout <<  (solve(0, 1, 1, 400)? 1: 0) << endl;
  }
}