Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、3問目を解説していきたいと思います。
問題名 【A – Range Flip Find Route】
入力
H：縦の長さ
W：横の長さ
S：長さWの文字列
考察
(1,1)→(H,W)にかけて、よい状態(白マス)だけを通りたいので、変換するべきマスは黒マスのみです。
また今回は、任意の区間、すなわち連続する黒マスは1回の処理で変換することができます。
i行目j列目までに行くのに必要な情報は、
- i-1行目j列目の情報(色情報、何回遷移したかの情報)
- i行目j-1列目の情報(色情報、何回遷移したかの情報)
の2つです。つまり一つ前の遷移の情報だけあればよいので、今回は動的計画法(dp)を使えば問題を解くことが可能です。
コード
from collections import deque
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
H,W = MI()
INF = float("inf")
box = []
for i in range(H):
A = S()
box.append(A)
# print(box[0][1])
dp = [[INF]* W for i in range(H)]
if box[0][0] == "#":
dp[0][0] = 1
else:
dp[0][0] = 0
for h in range(1,H):
if box[h][0] == box[h-1][0]:
dp[h][0] = dp[h-1][0]
else:
dp[h][0] = dp[h-1][0] + 1
for w in range(1,W):
if box[0][w] ==box[0][w-1]:
dp[0][w] = dp[0][w-1]
else:
dp[0][w] = dp[0][w-1] + 1
for h in range(1,H):
for w in range(1,W):
if box[h][w] == box[h-1][w]:
dp[h][w] = dp[h-1][w]
else:
dp[h][w] = dp[h-1][w]+1
if box[h][w] == box[h][w-1]:
dp[h][w] = min(dp[h][w-1],dp[h][w])
else:
dp[h][w] = min(dp[h][w-1]+1,dp[h][w])
if box[-1][-1] == "#":
dp[-1][-1] += 1
print(dp[-1][-1]//2)余談
今回、いけしゃあしゃあと記事を書いていますが、最初は全然解けませんでした。理由は動的計画法で解くところBFS(以下コード)で解こうとしたからです。僕は、一度決めてしまうと試行が狭まってしまいます。。途中、どこかでおかしいと思ったら問題を俯瞰してみるのは大事ですね・・
まとめ
今回の問題は、動的計画法を使う問題でした！自分は動的計画法とBFSの使い分けが苦手なので、今回の問題を通して勉強していきたいと思います。最後までお読みいただきありがとうございました！！
コメント