Problem:


Problem F: Line Puzzle

プログラミングでパズルを解いてみよう。

n &times; n の数字が格子状に並んでいる。数字のいくつかは丸で囲まれており、これらを起点と呼ぶことにする。パズルのルールは以下のとおりである：

各起点から縦・横に進む１本の線を引く（斜めには引けない）。

通った数字の和が起点の数字と同じになるように線を伸ばす。

線は枝分かれしてはいけない。

線はすでに引かれた数字を通ることはできない（線は交差してはいけない）。

線は２個以上の起点を通ることはできない。

下図に示すように、パズルのゴールはすべての起点を使い、すべての数字に線を引くことである。

あなたの仕事は、パズルを解くプログラムを作成することである。
ただしこの問題では、与えられたパズルが解けるものかどうかを判定するだけでよい。

Input

入力は複数のデータセットからなる。各データセットの形式は以下のとおりである：

n
n &times n の数字

n &times n の数字が与えられるパズルを示し、起点の数字は負の数として与えられる。

n が 0 のとき入力の終わりを示す。

n は 3 以上 8 以下、起点以外の数字は 1 以上 50 以下、起点は -50 以上 -1 以下であると仮定してよい。また、入力されるパズルの性質として以下のことを仮定してよい：

与えられるパズルの各行、各列には最低でも１つの起点がある。

起点の個数は、全体の数字の個数 (n &times; n) の 20 % から 40 % 程度である。

Output

各データセットに対して、パズルが解けるものであれば "YES" を、そうでなければ "NO" と１行に出力せよ。

Sample Input

3
-3 1 1
2 -4 1
2 1 -1
3
-4 1 1
1 1 -6
1 -5 3
4
-8 6 -2 1
2 -7 -2 1
1 -1 1 1
1 1 1 -5
6
2 2 3 -7 3 2
1 -10 1 1 3 2
2 6 5 2 -6 1
3 4 -23 2 2 5
3 3 -6 2 3 7
-7 2 3 2 -5 -13
6
2 2 3 -7 3 2
1 -10 1 1 3 2
2 6 5 2 -6 1
3 4 -23 2 2 5
3 3 -6 2 3 7
-7 2 3 2 -5 -12
0

Output for the Sample Input

YES
NO
NO
YES
NO



Sample input:
3
-3 1 1
2 -4 1
2 1 -1
3
-4 1 1
1 1 -6
1 -5 3
4
-8 6 -2 1
2 -7 -2 1
1 -1 1 1
1 1 1 -5
6
2 2 3 -7 3 2
1 -10 1 1 3 2
2 6 5 2 -6 1
3 4 -23 2 2 5
3 3 -6 2 3 7
-7 2 3 2 -5 -13
6
2 2 3 -7 3 2
1 -10 1 1 3 2
2 6 5 2 -6 1
3 4 -23 2 2 5
3 3 -6 2 3 7
-7 2 3 2 -5 -12
0


Sample output:
YES
NO
NO
YES
NO

Submission status: Time Limit Exceeded

Solution code:
def dfs(a,i,j,rest,vis):
  if i<0 or len(a)<=i or j<0 or len(a[i])<=j: return False
  if a[i][j]<0 or rest<a[i][j] or vis[i][j]: return False
  vis[i][j]=1
  rest-=a[i][j]
  if rest==0:
    if start(a,vis):
      return True
  else:
    for di,dj in zip([-1,1,0,0],[0,0,-1,1]):
      if dfs(a,i+di,j+dj,rest,vis):
        return True
  vis[i][j]=0
  return False

def start(a,vis):
  for i in range(len(a)):
    for j in range(len(a[i])):
      if a[i][j]<0 and not vis[i][j]:
        vis[i][j]=1
        for di,dj in zip([-1,1,0,0],[0,0,-1,1]):
          if dfs(a,i+di,j+dj,-a[i][j],vis):
            return True
        vis[i][j]=0
        return False
  return True

while 1:
  n=int(input())
  if n==0: break
  a=[list(map(int,input().split())) for _ in range(n)]

  if sum(x for row in a for x in row):
    print("NO")
    continue

  vis=[[0]*n for _ in range(n)]
  print("YES" if start(a,vis) else "NO")

Submission status: Time Limit Exceeded

Solution code:
def dfs(a,i,j,ss,si,rest,vis):
  if i<0 or len(a)<=i or j<0 or len(a[i])<=j or vis[i][j]: return False
  if a[i][j]<0 and (i,j)==ss[si]:
    vis[i][j]=1
    for di,dj in zip([-1,1,0,0],[0,0,-1,1]):
      if dfs(a,i+di,j+dj,ss,si,-a[i][j],vis):
        return True
    vis[i][j]=0
  elif a[i][j]>0 and rest>=a[i][j]:
    rest-=a[i][j]
    vis[i][j]=1
    if rest==0:
      if si+1==len(ss): return True
      ni,nj=ss[si+1]
      if dfs(a,ni,nj,ss,si+1,-a[i][j],vis):
        return True
    else:
      for di,dj in zip([-1,1,0,0],[0,0,-1,1]):
        if dfs(a,i+di,j+dj,ss,si,rest,vis):
          return True
    vis[i][j]=0
  return False

while 1:
  n=int(input())
  if n==0: break
  a=[list(map(int,input().split())) for _ in range(n)]

  if sum(x for row in a for x in row):
    print("NO")
    continue

  ss=[(i,j) for i in range(n) for j in range(n) if a[i][j]<0]
  vis=[[0]*n for _ in range(n)]
  i,j=ss[0]
  print("YES" if dfs(a,i,j,ss,0,-a[i][j],vis) else "NO")

Submission status: Time Limit Exceeded

Solution code:
di=(-1,1,0,0)
dj=(0,0,-1,1)

def solve(a,ss,i,j,si,rest,vis):
  n=len(a)
  if i<0 or n<=i or j<0 or n<=j or vis[i][j]: return False
  if a[i][j]<0:
    if ss[si]!=(i,j): return False
    vis[i][j]=-1-si
    for k in range(4):
      ni,nj=i+di[k],j+dj[k]
      if solve(a,ss,ni,nj,si,rest,vis): return True
    vis[i][j]=0
  else:
    if rest<a[i][j]: return False
    vis[i][j]=-1-si
    rest-=a[i][j]
    if rest==0:
      si+=1
      if si==len(ss): return True
      ni,nj=ss[si]
      if solve(a,ss,ni,nj,si,-a[ni][nj],vis): return True
    else:
      for k in range(4):
        ni,nj=i+di[k],j+dj[k]
        if solve(a,ss,ni,nj,si,rest,vis): return True
    vis[i][j]=0
  return False

while 1:
  n=int(input())
  if n==0: break
  a=[list(map(int,input().split())) for _ in range(n)]

  if sum(x for row in a for x in row):
    print("NO")
    continue

  ss=[(i,j) for i in range(n) for j in range(n) if a[i][j]<0]
  vis=[[0]*n for _ in range(n)]
  i,j=ss[0]
  if solve(a,ss,i,j,0,-a[i][j],vis):
    print("YES")
  else:
    print("NO")

Submission status: Accepted

Solution code:
board = []
used = []
v = []
n = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def set_v():
    global v
    for y in range(0, n):
        for x in range(0, n):
            if board[y][x] < 0:
                v += [(x, y)]
                used[y][x] = 1 

def solve(x, y, rest, s, k):
    if s == 0:
        if rest == 0:
            if k == len(v) - 1:
                return True
            return False
        if k < len(v) - 1:
            k1 = k + 1
            xx, yy = v[k1]
            used[y][x] = 1
            if solve(xx, yy, rest - 1, - board[yy][xx], k1):
                return True
            used[y][x] = 0
    if s <= 0 or k >= len(v):
        return False
    if board[y][x] > 0:
        used[y][x] = 1
    for d in range(0, 4):
        xx = x + dx[d]
        yy = y + dy[d]
        if 0 <= xx < n and 0 <= yy < n and used[yy][xx] == 0:
            if solve(xx, yy, rest - 1, s - board[yy][xx], k):
                return True
    if board[y][x] > 0:
        used[y][x] = 0
    return False



while True:
    board = []
    v = []
    line = input()
    n = int(line)
    if n == 0:
        break
    for _ in range(0, n):
        a = list(map(int, list(input().split())))
        board.append(a)
    used = [ [0] * n for _ in range(0, n)]
    set_v()
    x, y = v[0]
    print("YES" if solve(x, y, n * n - 1, - board[y][x], 0) else "NO")

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:break
  mp = [list(map(int, input().split())) for _ in range(n)]
  used = [[False] * n for _ in range(n)]
  
  inits = []
  for y in range(n):
    for x in range(n):
      if mp[y][x] < 0:
        inits.append((x, y, mp[y][x]))
        used[y][x] = True
  
  vec = ((0, 1), (-1, 0), (0, -1), (1, 0))
  
  def search(x, y, s, index, inits, end):
    if s == 0 and index == end:
      return True
    elif s == 0:
      x, y, s = inits[index]
      index += 1
    
    ret = False
    for dx, dy in vec:
      nx, ny = x + dx, y + dy
      if 0 <= nx < n and 0 <= ny < n and not used[ny][nx] and mp[ny][nx] + s <= 0:
        used[ny][nx] = True
        ret = ret or search(nx, ny, s + mp[ny][nx], index, inits, end)
        used[ny][nx] = False
    return ret
  
  if sum([sum(lst) for lst in mp]) != 0:
    print("NO")
  else:
    if search(0, 0, 0, 0, inits, len(inits)):
      print("YES")
    else:
      print("NO")