AOJ : 1034 - Line Puzzle
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1034
日本語の問題文なので省略.
アルゴリズム
深さ優先で全探索するだけで解ける.
プログラム
typedef pair<int,int> P; int n; int t[10][10],pass[10][10]; int dx[] = {-1,1,0,0}; int dy[] = {0,0,1,-1}; vector<P> v; bool solve(int x,int y,int rem,int sum,int vi){ if(sum == 0){ if(rem == 0){ if(v.size() - 1 == vi){ return true; } return false; } else if(vi < v.size()-1){ int nvi = vi + 1; pass[y][x] = vi+1; if(solve(v[nvi].second,v[nvi].first,rem-1,-t[v[nvi].first][v[nvi].second],nvi)) return true; pass[y][x] = 0; } } if(rem <= 0 || sum <= 0 || vi >= v.size()) return false; if(t[y][x]>0) pass[y][x] = vi+1; for(int i=0;i<4;i++){ int nx = x + dx[i]; int ny = y + dy[i]; if(0<=nx && nx<n && 0<=ny && ny<n && !pass[ny][nx]){ if(solve(nx,ny,rem-1,sum-t[ny][nx],vi)){ return true; } } } if(t[y][x]>0) pass[y][x] = 0; return false; } int main(void){ while(cin>>n,n){ memset(pass,0,sizeof(pass)); v.clear(); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>t[i][j]; if(t[i][j] < 0){ v.push_back(P(i,j)); pass[i][j] = v.size(); } } } cout<<(solve(v[0].second,v[0].first,n*n-1,-t[v[0].first][v[0].second],0) ? "YES" : "NO")<<endl; } return 0; }