読者です 読者をやめる 読者になる 読者になる

AOJ 1034 Line Puzzle

問題

Line Puzzle

解法

DFS。左上の起点から順番に走査していく。

心臓に悪いコード

int dy[] = {-1,0,1,0}, dx[] = {0,-1,0,1};
int n, used[8][8], p[8][8], res;

void dfs(int sum, int y, int x, int rest){
  if(res) return;

  if(sum == 0 && rest == 0){
    res = 1;
    return;
  }
  if(sum == 0){
    rep(i, n) rep(j, n){
      if(used[i][j]) continue;
      if(p[i][j]<0){
    used[i][j] = 1;
    dfs(-p[i][j], i, j, rest-1);
    used[i][j] = 0;
    return;
      }
    }
  }else{
    rep(d, 4){
      int ny = y + dy[d], nx = x + dx[d];
      if(ny < 0 || nx < 0 || ny >= n || nx >= n || used[ny][nx] || p[ny][nx] < 0 || p[ny][nx] > sum) continue;
      used[ny][nx] = 1;
      dfs(sum - p[ny][nx], ny, nx, rest-1);
      used[ny][nx] = 0;
    }
  }
}

int main(){
  while(scanf("%d", &n) && n){
    res = 0;
    memset(used, 0, sizeof(used));
    rep(i, n) rep(j, n) scanf("%d", &p[i][j]);

    dfs(0, 0, 0, n*n);
    puts(res?"YES":"NO");
  }
  return 0;
}