Problem:


 お土産購入計画 (Gifts)

問題

オーストラリアに旅行に来た JOI 君は様々な場所で観光を楽しみ，ついに帰国する日がやってきた．今，JOI 君は帰りの飛行機が出発する国際空港のある町にいる．この町は東西南北に区画整理されており，各区画には道，土産店，住宅，国際空港がある．
JOI 君は最も北西の区画から出発して最も南東の区画の国際空港を目指す．

JOI 君は今いる区画から隣り合った区画に移動することができるが，住宅のある区画には入ることはできない．また飛行機の時間に間に合わせるために，今いる区画の東か南の区画にのみ移動する．ただし，時間にはいくらか余裕があるため，K 回まで今いる区画の北か西の区画へ移動することができる．

JOI 君は土産店のある区画に入ると，日本の友人たちのためにお土産を買う．JOI 君は土産店について入念に下調べをしていたので，どの土産店に行ったら何個のお土産を買うことができるかが分かっている．JOI 君が購入できるお土産の個数の最大値を求めるプログラムを作成せよ．

ただし，お土産を買う時間は無視できるとし，同じ土産店に 2 度以上訪れたときは最初に訪れたときだけお土産を買う．

  入力

入力は 1 + H 行からなる．

1 行目には，3 つの整数 H, W, K (2 ≦ H ≦ 50, 2 ≦ W ≦ 50, 1 ≦ K ≦ 3) が空白を区切りとして書かれている．

続く H 行にはそれぞれ W 文字からなる文字列が書かれており，区画の情報を表す．北から i 番目，西から j 番目の区画を (i, j) と表す (1 ≦ i ≦ H, 1 ≦ j ≦ W)．
i 行目の j 番目の文字は，区画 (i, j) が道か国際空港である場合は '.' であり，住宅である場合は '#' である．
土産店である場合は '1', '2', ..., '9' のいずれかであり，その土産店で買うことができるお土産の個数を表す．

与えられる入力データにおいては，JOI 君がはじめにいる最も北西の区画が道であることは保証されている．また，JOI 君が国際空港にたどり着けることは保証されている．

  出力

JOI 君が購入できるお土産の個数の最大値を表す整数を 1 行で出力せよ．

  入出力例

入力例 1

  

5 4 2
...#
.#.#
.#73
8##.
....

出力例 1

11

入出力例 1 において，JOI 君は 3 回南へ進み区画 (4, 1) の土産店で買い物をした後，さらに南へ 1 回，東へ 3 回進み，そこから北へ 2 回進むことで区画 (3, 4) の土産店で買い物をする．最後に南へ 2 回進んで国際空港へたどり着くと，合計で 11 個のお土産を買うことができる．

入力例 2
  
  

4 4 3
.8#9
9.#.
.#9.
....

出力例 2

  

27

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5 4 2
...#
.#.#
.#73
8##.
....


Sample output:
11

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581

"""
import sys
from sys import stdin
from collections import deque
from copy import copy
input = stdin.readline


def solve(field, K):
    """

    :param field:
    :return:
    """
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    yorimichi = K
    purchased = set()
    max_gift = 0

    # ???????????????????????????????????°???????????´????????°????????§????????¢????±???????
    Q = deque()
    Q.append((0, 0, copy(purchased), yorimichi))
    while Q:
        cx, cy, purchased, yorimichi= Q.popleft()        #  ?????¨??°?????§?¨?
        if not '0' <= field[cy][cx] <= '9':
            field[cy][cx] = '@'
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (not 0 <= nx < X) or (not 0 <= ny < Y):
                continue
            elif field[ny][nx] != '#':
                if '0' <= field[ny][nx] <= '9':
                    purchased.add((nx, ny))
                    gift = 0
                    for gx, gy in purchased:
                        gift += int(field[gy][gx])
                    if gift > max_gift:
                        max_gift = gift

                if yorimichi > 1:
                    if dy[i] == -1 or dx[i] == -1:
                        Q.append((nx, ny, copy(purchased), yorimichi-1))
                    else:
                        Q.append((nx, ny, copy(purchased), yorimichi))

    return max_gift


def main(args):
    H, W, K = map(int, input().split())
    data = [input().strip('\n') for _ in range(H)]
    field = [list(x) for x in data] #  data????????????????????????????????????????????????
    result = solve(field, K)
    print(result)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581
"""
import sys
from sys import stdin
from collections import deque
from copy import copy
from collections import defaultdict
input = stdin.readline


def solve(field, K):
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    # d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    yorimichi = K
    purchased = set()
    visited = defaultdict(int)
    max_gift = 0

    goal = False
    Q = deque()
    Q.append((0, 0, copy(purchased), copy(visited), yorimichi, goal))
    while Q:
        cx, cy, purchased, visited, yorimichi, goal= Q.popleft()        #  ?????¨??°?????§?¨?
        key = '-'.join(map(str, (cx, cy)))
        visited[key] += 1
        if goal == True:
            gift = 0
            for gx, gy in purchased:
                gift += int(field[gy][gx])
            if gift > max_gift:
                max_gift = gift
        if not '0' <= field[cy][cx] <= '9':
            field[cy][cx] = '@'
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if nx == X-1 and ny == Y-1:
                goal = True
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (not 0 <= nx < X) or (not 0 <= ny < Y) or field[ny][nx] == '#':
                continue
            key = '-'.join(map(str, (cx, cy)))
            if visited[key] > 2:
                continue

            if dy[i] == -1 or dx[i] == -1:
                if yorimichi > 0:
                    temp = copy(purchased)
                    if '0' <= field[ny][nx] <= '9':
                        temp.add((nx, ny))
                    Q.append((nx, ny, copy(temp), copy(visited), yorimichi-1, goal))
            else:
                temp = copy(purchased)
                if '0' <= field[ny][nx] <= '9':
                    temp.add((nx, ny))
                Q.append((nx, ny, copy(temp), copy(visited), yorimichi, goal))
    return max_gift


def main(args):
    # data = []
    # data.append('...#')
    # data.append('.#.#')
    # data.append('.#73')
    # data.append('8##.')
    # data.append('....')
    # K = 2
    # field = [list(x) for x in data] #  data????????????????????????????????????????????????
    # result = solve(field, K)
    # print(result)

    # data = []
    # data.append('.##9###.')
    # data.append('.#6.9..3')
    # data.append('.#378.#2')
    # data.append('....#9..')
    # data.append('##4..6.#')
    # data.append('4...5###')
    # data.append('4##.#..1')
    # data.append('5..2..#.')
    K = 3
    # field = [list(x) for x in data] #  data????????????????????????????????????????????????
    # result = solve(field, K)
    # print(result)


    # H, W, K = map(int, input().split())
    # data = [input().strip('\n') for _ in range(H)]
    # field = [list(x) for x in data] #  data????????????????????????????????????????????????
    # result = solve(field, K)
    # print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
def main():
  def bfs(x, y, k, score):
    if (x, y) == (w, h) and k == 0:
      return score
    score += mp[y][x]
    tmp = mp[y][x]
    mp[y][x] = 0
    ret = -1
    if k >= 1:
      if mp[y][x - 1] != -1:
        ret = max(ret, bfs(x - 1, y, k - 1, score))
      if mp[y - 1][x] != -1:
        ret = max(ret, bfs(x, y - 1, k - 1, score))
    if mp[y][x + 1] != -1:
      ret = max(ret, bfs(x + 1, y, k, score))
    if mp[y + 1][x] != -1:
      ret = max(ret, bfs(x, y + 1, k, score))
  
    mp[y][x] = tmp
    return ret
  
  h, w, k = map(int, input().split())
  mp = [list("#" + input() + "#") for _ in range(h)]
  mp.insert(0, ["#"] * (w + 2))
  mp.append(["#"] * (w + 2))
  for y in range(h + 2):
    for x in range(w + 2):
      if "1" <= mp[y][x] <= "9":
        mp[y][x] = int(mp[y][x])
      elif mp[y][x] == ".":
        mp[y][x] = 0
      else:
        mp[y][x] = -1
  print(bfs(1, 1, k, 0))

main()

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581

"""
import sys
from sys import stdin
from collections import deque
from copy import copy
input = stdin.readline


def solve(field, K):
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    # d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    yorimichi = K
    purchased = set()
    max_gift = 0

    Q = deque()
    Q.append((0, 0, copy(purchased), yorimichi))
    while Q:
        cx, cy, purchased, yorimichi= Q.popleft()        #  ?????¨??°?????§?¨?
        if not '0' <= field[cy][cx] <= '9':
            field[cy][cx] = '@'
        if cx == X-1 and cy == Y-1:
            gift = 0
            for gx, gy in purchased:
                gift += int(field[gy][gx])
            if gift > max_gift:
                max_gift = gift

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (not 0 <= nx < X) or (not 0 <= ny < Y) or field[ny][nx] == '#':
                continue
            if dy[i] == -1 or dx[i] == -1:
                if yorimichi > 0:
                    temp = copy(purchased)
                    if '0' <= field[ny][nx] <= '9':
                        temp.add((nx, ny))
                    Q.append((nx, ny, copy(temp), yorimichi-1))
            else:
                temp = copy(purchased)
                if '0' <= field[ny][nx] <= '9':
                    temp.add((nx, ny))
                Q.append((nx, ny, copy(temp), yorimichi))
    return max_gift


def main(args):
    # data = []
    # data.append('...#')
    # data.append('.#.#')
    # data.append('.#73')
    # data.append('8##.')
    # data.append('....')
    # K = 2
    # field = [list(x) for x in data] #  data????????????????????????????????????????????????
    # result = solve(field, K)
    # print(result)
    #
    # data = []
    # data.append('.##9###.')
    # data.append('.#6.9..3')
    # data.append('.#378.#2')
    # data.append('....#9..')
    # data.append('##4..6.#')
    # data.append('4...5###')
    # data.append('4##.#..1')
    # data.append('5..2..#.')
    # K = 3
    # field = [list(x) for x in data] #  data????????????????????????????????????????????????
    # result = solve(field, K)
    # print(result)

    H, W, K = map(int, input().split())
    data = [input().strip('\n') for _ in range(H)]
    field = [list(x) for x in data] #  data????????????????????????????????????????????????
    result = solve(field, K)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581
"""
import sys
from sys import stdin
from collections import deque
from copy import copy
from collections import defaultdict
input = stdin.readline


def solve(field, K):
    # ????????????????§????????????´????????§?¨?????????????
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    # ??°???????????????(?§????????????£????????????????????????????????§??????????????¨)
    Y = len(field)
    X = len(field[0])
    # d = [[float('inf')] * X for _ in range(Y)] #  ??????????????°?????????????????¢???INF??§?????????
    yorimichi = K
    purchased = set()
    visited = defaultdict(int)
    max_gift = 0

    goal = False
    Q = deque()
    Q.append((0, 0, copy(purchased), copy(visited), yorimichi, goal))
    while Q:
        cx, cy, purchased, visited, yorimichi, goal= Q.popleft()        #  ?????¨??°?????§?¨?
        key = '-'.join(map(str, (cx, cy)))
        visited[key] += 1
        if goal == True:
            gift = 0
            for gx, gy in purchased:
                gift += int(field[gy][gx])
            if gift > max_gift:
                max_gift = gift
        if not '0' <= field[cy][cx] <= '9':
            field[cy][cx] = '@'
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if nx == X-1 and ny == Y-1:
                goal = True
            # ?§?????????? ??°????????????????????????????????? and ?£?????????£???????????? and ??¢?????¢?´¢?????§?????? ??´???
            if (not 0 <= nx < X) or (not 0 <= ny < Y) or field[ny][nx] == '#':
                continue
            key = '-'.join(map(str, (cx, cy)))
            if visited[key] > 2:
                continue

            if dy[i] == -1 or dx[i] == -1:
                if yorimichi > 0:
                    temp = copy(purchased)
                    if '0' <= field[ny][nx] <= '9':
                        temp.add((nx, ny))
                    Q.append((nx, ny, copy(temp), copy(visited), yorimichi-1, goal))
            else:
                temp = copy(purchased)
                if '0' <= field[ny][nx] <= '9':
                    temp.add((nx, ny))
                Q.append((nx, ny, copy(temp), copy(visited), yorimichi, goal))
    return max_gift


def main(args):
    # data = []
    # data.append('...#')
    # data.append('.#.#')
    # data.append('.#73')
    # data.append('8##.')
    # data.append('....')
    # K = 2
    # field = [list(x) for x in data] #  data????????????????????????????????????????????????
    # result = solve(field, K)
    # print(result)

    # data = []
    # data.append('.##9###.')
    # data.append('.#6.9..3')
    # data.append('.#378.#2')
    # data.append('....#9..')
    # data.append('##4..6.#')
    # data.append('4...5###')
    # data.append('4##.#..1')
    # data.append('5..2..#.')
    K = 3
    # field = [list(x) for x in data] #  data????????????????????????????????????????????????
    # result = solve(field, K)
    # print(result)


    H, W, K = map(int, input().split())
    data = [input().strip('\n') for _ in range(H)]
    field = [list(x) for x in data] #  data????????????????????????????????????????????????
    result = solve(field, K)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)

def check(y,x):
    if 0<=x<=w-1 and 0<=y<=h-1 and g[y][x]!="#":
        return True
    return False

def dfs(y,x,cnt,v):
    global ans
    if cnt>k:return -1
    if y==h-1 and x==w-1 and cnt==k:
        return v
    if cnt==k:
        for i in xrange(4):
            if i==2 or i==3:continue
            nxx=x+dx[i]
            nyy=y+dy[i]
            if not check(nyy,nxx):continue
            if g[nyy][nxx]!=".":
                su=0
                f=0
                if not visited[nyy][nxx]:
                    su=int(g[nyy][nxx])
                    visited[nyy][nxx]=True
                    f=1
                ans=max(ans,dfs(nyy,nxx,cnt,v+su))
                if f==1:
                    visited[nyy][nxx]=False
            else:
                ans=max(ans,dfs(nyy,nxx,cnt,v))
    if y==h-1 and x==w-1 and cnt==k:
        return v
    for i in xrange(4):
        nxx=x+dx[i]
        nyy=y+dy[i]
        if not check(nyy,nxx):continue
        if i==0 or i==1:
            if g[nyy][nxx]!=".":
                su=0
                f=0
                if not visited[nyy][nxx]:
                    su=int(g[nyy][nxx])
                    visited[nyy][nxx]=True
                    f=1
                ans=max(ans,dfs(nyy,nxx,cnt,v+su))
                if f==1:
                    visited[nyy][nxx]=False
            else:
                ans=max(ans,dfs(nyy,nxx,cnt,v))
        else:
            if g[nyy][nxx]!=".":
                su=0
                f=0
                if not visited[nyy][nxx]:
                    su=int(g[nyy][nxx])
                    visited[nyy][nxx]=True
                    f=1
                ans=max(ans,dfs(nyy,nxx,cnt+1,v+su))
                if f==1:
                    visited[nyy][nxx]=False
            else:
                ans=max(ans,dfs(nyy,nxx,cnt+1,v))
    return ans


h,w,k=map(int,raw_input().split())
g=[raw_input() for _ in xrange(h)]
dx=(1,0,-1,0)
dy=(0,1,0,-1)
visited=[[False]*w for _ in xrange(h)]
ans=0
ans=dfs(0,0,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
INF = 9

h, w, k = map(int,input().split())
maps = [list("#" * (w + 2))]
for i in range(h):
  maps.append(list("#" + input() + "#"))
maps.append(list("#" * (w + 2)))

#スタートからそのマスまでに何度逆走する必要があるかのマップ
#root_map = [[INF] * (w + 2) for i in range(h + 2)]

#そのマスからゴールまでに何度逆走する必要があるかのマップ
reverse_map = [[INF] * (w + 2) for i in range(h + 2)]

#def root_search(x, y, score):
#  if score < root_map[x][y]:
#    root_map[x][y] = score
#    if maps[x - 1][y] != "#":
#      root_search(x - 1, y, score + 1)
#    if maps[x + 1][y] != "#":
#      root_search(x + 1, y, score)
#    if maps[x][y - 1] != "#":
#      root_search(x, y - 1, score + 1)
#    if maps[x][y + 1] != "#":
#      root_search(x, y + 1, score)
#
def reverse_search(x, y, score):
  if score < reverse_map[x][y]:
    reverse_map[x][y] = score
    if maps[x - 1][y] != "#":
      reverse_search(x - 1, y, score)
    if maps[x + 1][y] != "#":
      reverse_search(x + 1, y, score + 1)
    if maps[x][y - 1] != "#":
      reverse_search(x, y - 1, score)
    if maps[x][y + 1] != "#":
      reverse_search(x, y + 1, score + 1)

def search(x, y, score, rest):
  if rest < reverse_map[x][y]:
    return 0

  temp = maps[x][y]
  if maps[x][y] in [str(i) for i in range(1,10)]:
    score += int(maps[x][y])
    maps[x][y] = "."
  a = b = c = d = 0
  if rest > 0 and maps[x - 1][y] != "#":
    a = search(x - 1, y, score, rest - 1)
  if maps[x + 1][y] != "#":
    b = search(x + 1, y, score, rest)
  if rest > 0 and maps[x][y - 1] != "#":
    c = search(x, y - 1, score, rest - 1)
  if maps[x][y + 1] != "#":
    d = search(x, y + 1, score, rest)
  ret = max(score, a, b, c, d)
  maps[x][y] = temp
  return ret

#root_search(1, 1, 0)
reverse_search(h, w, 0)


print(search(1,1,0,k))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
INF = 9

h, w, k = map(int,input().split())
maps = [list("#" * (w + 2))]
for i in range(h):
  maps.append(list("#" + input() + "#"))
maps.append(list("#" * (w + 2)))

#スタートからそのマスまでに何度逆走する必要があるかのマップ
#root_map = [[INF] * (w + 2) for i in range(h + 2)]

#そのマスからゴールまでに何度逆走する必要があるかのマップ
reverse_map = [[INF] * (w + 2) for i in range(h + 2)]

#def root_search(x, y, score):
#  if score < root_map[x][y]:
#    root_map[x][y] = score
#    if maps[x - 1][y] != "#":
#      root_search(x - 1, y, score + 1)
#    if maps[x + 1][y] != "#":
#      root_search(x + 1, y, score)
#    if maps[x][y - 1] != "#":
#      root_search(x, y - 1, score + 1)
#    if maps[x][y + 1] != "#":
#      root_search(x, y + 1, score)
#
def reverse_search(x, y, score):
  if score < reverse_map[x][y]:
    reverse_map[x][y] = score
    if maps[x - 1][y] != "#":
      reverse_search(x - 1, y, score)
    if maps[x + 1][y] != "#":
      reverse_search(x + 1, y, score + 1)
    if maps[x][y - 1] != "#":
      reverse_search(x, y - 1, score)
    if maps[x][y + 1] != "#":
      reverse_search(x, y + 1, score + 1)

def search(x, y, score, rest):
  if rest < reverse_map[x][y]:
    return 0

  temp = maps[x][y]
  if maps[x][y] in [str(i) for i in range(1,10)]:
    score += int(maps[x][y])
    maps[x][y] = "."
  a = b = c = d = 0
  if rest > 0 and maps[x - 1][y] != "#":
    a = search(x - 1, y, score, rest - 1)
  if maps[x + 1][y] != "#":
    b = search(x + 1, y, score, rest)
  if rest > 0 and maps[x][y - 1] != "#":
    c = search(x, y - 1, score, rest - 1)
  if maps[x][y + 1] != "#":
    d = search(x, y + 1, score, rest)
  ret = max(score, a, b, c, d)
  maps[x][y] = temp
  return ret

#root_search(1, 1, 0)
reverse_search(h, w, 0)


print(search(1,1,0,k))