AOJ 1034 Line Puzzle
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1034
日本語参照。
深さ優先探索。左上の起点から順番に埋めていき、経路の確定した起点を再び使わないことで枝刈りが出来ていると思います。
何だか分かりにくいCPPになってしまいました。
int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; bool ans; int n; bool vis[8][8]; int in[8][8]; void dfs(int rest,int x,int y,int visnum){ if(ans)return; if(visnum==0 && rest==0){ ans=true; return; } if(rest==0){ rep(i,n)rep(j,n){ if(vis[i][j])continue; if(in[i][j]<0){ vis[i][j]=true; dfs(-in[i][j],i,j,visnum-1); vis[i][j]=false; return; } } }else{ rep(i,4){ int nx=x+dx[i],ny=y+dy[i]; if(nx<0 || n<=nx || ny<0 || n<=ny || vis[nx][ny] || in[nx][ny]<0 || in[nx][ny]>rest)continue; vis[nx][ny]=true; dfs(rest-in[nx][ny],nx,ny,visnum-1); vis[nx][ny]=false; } } } main(){ while(cin>>n,n){ ans=false; memset(vis,0,sizeof(vis)); rep(i,n)rep(j,n)cin>>in[i][j]; dfs(0,0,0,n*n); if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl; } }