AOJ 1034 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; }