白駿1937欲張りパンダ

白駿1937パンダ問題

ソース:https://www.acmicpc.net/problem/1937

Pythonコード

import sys

N = int(sys.stdin.readline())
board = []

for i in range(N):
  board.append(list(map(int,sys.stdin.readline().split())))

dp = [[0 for _ in range(N)] for _ in range(N)]

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

def recursive():  
  result = 0
  for i in range(N):
    for v in range(N):
      dfs(i, v)
      result = max(result, dp[i][v])
  print(result)

def dfs(r, c):  
  find = False
  for i in range(4):
    new_r = r + dy[i]
    new_c = c + dx[i]
    if new_r < 0 or new_r >= N or new_c < 0 or new_c >= N:
      continue
    else:
      if board[r][c] < board[new_r][new_c]:
        find = True
        if dp[new_r][new_c] != 0:
          dp[r][c] = max(dp[r][c], dp[new_r][new_c]+1)
        else:
          dp[r][c] = max(dp[r][c], dfs(new_r, new_c)+1)
  
  if find == False:
    dp[r][c] = 1
  return dp[r][c]

recursive()

解答方法

最初はbfsナビゲーションパスを使用しようとしたが、失敗したのは最長パスを求めることだった.「アクセス」がリストされていても、bfsによるナビゲーションでは最長の生存経路は保証されません.
そこで,再帰関数により各選択の最長生存経路を見つけようとした.これでタイムアウトが発生し、この問題を解決するために
dpという名前のリストを作成し、計算の重複を回避します.
したがって、dpリストは、各座標に到達したときに歩ける最長の生存経路を示します.このように、新しい座標系にパンダがいても、計算されたdp座標に達すると、その値が加算され、再帰関数が終了します.
また、ジャイアントパンダは竹が以前より多くの場所にしか行かないため、もう1つの経路を通ることはないので、アクセスリストを管理する必要はありません.