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