Problem 1158 : ICPC: Intelligent Congruent Partition of Chocolate

Problem F: ICPC: Intelligent Congruent Partition of Chocolate
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1158

問題概要

チョコレートを連結で合同な二つのチョコレートにわけろ。裏返しにして一致してもよいとする。

解法

DFS.
探索開始地点、方向全部決め打ち。
オーダー、36＊36＊（18＋36）＊8くらい？

ソース

#include<iostream>
#include<algorithm>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
#define mp make_pair

 using namespace std;
 pair<int, int> D[4], TD[4];
 void init(){
   D[0] = mp(-1, 0);
   D[1] = mp(0, 1);
   D[2] = mp(1, 0);
   D[3] = mp(0, -1);  
 }

int NUM, H, W, t[10][10];
bool visited[10][10];
inline bool invalid(int y, int x, int ty, int tx){
   if(y < 0 || x< 0 || y >= H || x >= W)return true;
   if(ty < 0 || tx< 0 || ty >= H || tx >= W)return true;
   if(y == ty && x == tx)return true;
   if(visited[y][x] || visited[ty][tx])return true;
   if(t[y][x] == 0 || t[ty][tx] == 0)return true;
   return false;
 }
bool dfs(int y, int x, int ty, int tx, int &cnt){
  cnt++;
  if(cnt *2 == NUM)return true;
  visited[y][x] = visited[ty][tx] = true;
  rep(i, 4){
    int ny = y + D[i].first;
    int nx = x + D[i].second;
    int nty = ty + TD[i].first;
    int ntx = tx + TD[i].second;
    if(invalid(ny, nx, nty, ntx))continue;
    if(dfs(ny, nx, nty, ntx, cnt))return true;
  }
  return false;
}

bool input(){
  cin >> W >> H;
  if(W == 0 && H == 0)return false;
  NUM = 0;
  rep(i, H){
    rep(j, W){
      cin >> t[i][j];
      if(t[i][j] == 1)NUM++;
    }
  }
  rep(i ,H){
    rep(j, W){
      visited[i][j] = false;
    }
  }
  return true;
}

string solve(){
  rep(i, 4)TD[i] = D[i];
  rep(base, 2){
    rep(r, 4){
      rotate(TD, TD+1, TD+4);
      rep(i, H){
        rep(j, W){
          if(t[i][j] == 0)continue;
          rep(k, H){
            rep(l, W){
              if(k == i && l == j)continue;
              if(t[k][l] == 0)continue;
              int cnt = 0;
              rep(y, H){
                rep(x, W){
                  visited[y][x] = false;
                }
              }
              if(dfs(i, j, k, l, cnt))return "YES";
            }
          }
        }
      }
    }
    TD[1] = D[3];
    TD[3] = D[1];
  }
  return "NO";
}

int main(){
  init();
  while(input())cout << solve() << endl;
  return 0;
}