Alien Messages AC

AOJ0236.cpp

#include<cstdio>
#include<cstring>

using namespace std;

int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};
int F[9][9], C[9][9], V[9][9], cnt, sx, sy;

bool dfs(int y, int x, int visited)
{
  for(int i=0; i<4; ++i) {
    int nx = x+dx[i], ny = y+dy[i];
    if(visited == cnt && nx == sx && ny == sy)
      return true;
    if(F[ny][nx] == 1 || V[ny][nx] == 1)
      continue;
    V[ny][nx] = 1;
    if(dfs(ny, nx, visited+1))
      return true;
    V[ny][nx] = 0;
  }
  return false;
}

int main()
{
  int W, H;
  while(scanf("%d%d", &W, &H), W||H) {
    memset(V, 0, sizeof(V));
    for(int i=0; i<=H+1; ++i)
      for(int j=0; j<=W+1; ++j)
	F[i][j] = 1;

    cnt = 0;
    for(int i=1; i<=H; ++i) {
      for(int j=1; j<=W; ++j) {
	scanf("%d", &F[i][j]);
	if(F[i][j] == 0)
	  cnt++;
      }
    }

    int parity = 0;
    for(int i=1; i<=H; ++i)
      for(int j=1; j<=W; ++j)
	if(F[i][j] == 0)
	  parity += ((i+j)%2 ? 1 : -1);
    if(parity != 0) {
      puts("No");
      continue;
    }

    bool dead_end = false;
    for(int i=1; i<=H; ++i) {
      for(int j=1; j<=W; ++j) {
	if(F[i][j] == 1)
	  continue;
	C[i][j] = 0;
	for(int k=0; k<4; ++k)
	  if(F[i+dy[k]][j+dx[k]] == 1)
	    C[i][j]++;
	if(C[i][j] == 3)
	  dead_end = true;
      }
    }
    if(dead_end) {
      puts("No");
      continue;
    }

    bool end = false;
    for(int i=1; !end && i<=H; ++i) {
      for(int j=1; !end && j<=W; ++j) {
	if(F[i][j] == 1)
	  continue;
	sx = j;
	sy = i;
	V[sy][sx] = 1;
	if(dfs(i, j, 1))
	  puts("Yes");
	else
	  puts("No");
	end = true;
      }
    }
    if(!end)
      puts("No");
  }
  return 0;
}