AOJ 0236 : Alien Messages

問題リンク : Alien Messages | Aizu Online Judge

問題概要 : 略

解法 :
枝刈り探索
まず、初期状態で次数が１のマスが存在したら No
空のマスの数を数えてその数が奇数だったら No
これらに該当しない場合はDFSで探索する
h*wのブール型の2次元配列を用意し、バックトラックで訪れたマスにtrueを入れてダメだったらfalseに戻していく
すべてのマスを1回だけ訪れた後、そのマスがスタートのマスと隣接していれば Yes
次のマスに移る前に、そこに訪れた場合ちゃんとスタートへ戻れるかをチェックする
これだけではTLEだったので、もうひとつ枝刈り
未だに訪れていないマスでスタートと次に行く場所に隣接していないマスのうち、次数が１のものが存在したら枝刈り
ここでの次数はあるマスに隣接している４つのマスのうち、未だに訪れてない空のセルの数のことです

コード:

#include<bits/stdc++.h>

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

using namespace std;

struct Edge { int next, dir; };

int w,h,sp;
bool field[20][20];
vector<Edge> G[500];
bool visited[500],used[500];
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};

bool isValid(int x,int y) { return 0 <= x && x < w && 0 <= y && y < h; }

bool check2(int cur){
  rep(i,h*w) used[i] = false;
  rep(i,h) rep(j,w) if( field[i][j] || visited[j+i*w] ) used[j+i*w] = true;
  deque<int> deq;
  deq.push_back(cur);
  used[sp] = false;
  used[cur] = true;
  while( !deq.empty() ){
    int v = deq.front(); deq.pop_front();
    if( v == sp ) return true;
    rep(i,(int)G[v].size()) {
      int next = G[v][i].next;
      if( used[next] ) continue;
      used[next] = true;
      deq.push_back(next);
    }
  }
  return false;
}


bool check3(int cur){
  int counter;
  rep(i,h) rep(j,w) if( !field[i][j] && !visited[i*w+j] ){
    counter = 0;
    rep(k,4){
      int nx = j + dx[k], ny = i + dy[k];
      if( !isValid(nx,ny) ) continue;
      if( field[ny][nx] ) continue;
      if( visited[ny*w+nx] ) continue;
      ++counter;
    }
    if( counter == 1 ) {
      int outer = 0;
      int diff_x = abs(sp%w-j), diff_y = abs(sp/w-i);
      if( diff_x+diff_y <= 1 ) ++outer;
      diff_x = abs(cur%w-j), diff_y = abs(cur/w-i);
      if( diff_x+diff_y <= 1 ) ++outer;
      if( outer == 0 ) return false;
    }
  }
  return true;
}

bool dfs(int cur,int remain){
  if( remain == 0 ) {
    int diff_x = abs( cur % w - sp % w ), diff_y = abs( cur / w - sp / w );
    if( diff_x+diff_y == 1 ) return true;
    return false;
  }
  
  rep(i,(int)G[cur].size()){
    int next = G[cur][i].next;
    if( visited[next] ) continue;
    if( !check2(next) ) continue;
    if( !check3(next) ) continue;
    visited[next] = true;
    if( dfs(next,remain-1) ) return true;
    visited[next] = false;
  }

  return false;
}

void compute(){
  sp = -1;
  rep(i,h*w) G[i].clear(), visited[i] = false;
  rep(y,h) rep(x,w) if( !field[y][x] ){
    if( sp == -1 ) sp = x + y * w;
    rep(i,4){
      int nx = x + dx[i], ny = y + dy[i];
      if( !isValid(nx,ny) ) continue;
      if( field[ny][nx]   ) continue;
      G[x+y*w].push_back((Edge){nx+ny*w,i});
    }
  }

  rep(i,h*w) if( G[i].size() == 1 ) { puts("No"); return; }
  
  int remain = 0;
  rep(i,h) rep(j,w) if( !field[i][j] ) ++remain;
  visited[sp] = true;
  if( ( remain & 1 ) || remain == 0 ) { puts("No"); return; }
  puts(dfs(sp,remain-1)?"Yes":"No");
}

int main(){
  while( cin >> w >> h, w|h ){
    rep(i,h) rep(j,w) cin >> field[i][j];
    compute();
  }
  return 0;
}