Problem 1034 : Line Puzzle

Problem F: Line Puzzle
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1034

問題概要

８　８のグリッドがあって、始点になりうる点という点がいくつか存在している。
その始点から４方向に何回でも屈折できる線を重ならないように伸ばしたとき、
その通った数字の合計が始点の数字と等しくなるよう線をひく。
すべての始点から線をひくことができ、
かつ、すべてのマスに線を引くことができるか。

解法

探索。
DFS。
始点一個一個を見ていけばよい。
始点を決める関数とそこから線を引く関数で二重再帰的なことをした。

ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

using namespace std;

const int N = 8;

int t[N][N], n;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
bool visited[N][N];

bool searchBegin();

bool searchLine(int y, int x, int sum){
  visited[y][x] = true;
  if(sum == 0){
    if(searchBegin())return true;
  }
  if(sum >= 0){
    visited[y][x] = false;
    return false;
  }
  rep(i, 4){
    int ny = y + dy[i], nx = x + dx[i];
    if(ny < 0 || nx < 0 || ny >= n || nx >= n)continue;
    if(t[ny][nx] < 0 || visited[ny][nx])continue;
    if(searchLine(ny, nx, sum + t[ny][nx]))return true;
  }
  visited[y][x] = false;
  return false;
}


bool searchBegin(){
  bool end = true;
  rep(i, n){
    rep(j, n){
      if(visited[i][j])continue;
      end = false; 
      if( t[i][j] > 0)continue;   
      return searchLine(i, j, t[i][j]);
    } 
  }
  return end;
}


main(){
  while(cin >> n){
    if(n == 0)break;
    rep(i, n){
      rep(j, n){
	cin >> t[i][j];
	visited[i][j] = false;
      }
    }
    if(searchBegin())cout <<  "YES" << endl;
    else cout << "NO" << endl;
  }
}