TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.   For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:      * f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.  Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Submission attempts (in order):
from sys import stdin
mod = 998244353
def solveAsPolynomial():
    from numpy import *
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    ans = 0
    f = np.zeros(S+1,int64)
    for A in a:
        
        f[0] += 1#f+1
        f[A:] += f[:-A].copy()#f*(1+x**A)
        f %= mod
        ans += f[S]
        
        ans %= mod
    return ans
def main():
  ans = solveAsPolynomial()
  print(ans)
if __name__ =="__main__":
  main()

import numpy as np
mod = 998244353
def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    a = np.asarray(a)
    dp = np.zeros((N+1,S+1,3))
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0] ;dp[i+1][j][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(dp[N][S][2])
if __name__ == "__main__":
    main()

from sys import stdin
mod = 998244353
def solveAsPolynomial():
    import numpy as np
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    ans = 0
    f = np.zeros(S+1,np.int64)
    for A in a:
        
        f[0] += 1#f+1
        f[A:] += f[:-A].copy()#f*(1+x**A)
        f %= mod
        ans += f[S]
        
        ans %= mod
    return ans
def main():
  ans = solveAsPolynomial()
  print(ans)
if __name__ =="__main__":
  main()


Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.   For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:      * f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.  Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Submission attempts (in order):
import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
 

m = np.zeros((S+1,3))
p = np.zeros((S+1,3))
p[0,0] = 1


for i in range(1,N+1):
    
    
    m[:,0] = p[:,0]
    m[:,1] = p[:,0] + p[:,1]  
    m[:,2] = p[:,0] + p[:,1] + p[:,2]  

    
    m[x[i]:,1] += p[:-x[i-1],0] + p[:-x[i-1],1]
    m[x[i]:,2] += p[:-x[i-1],0] + p[:-x[i-1],1]

    p[:,0] = m[:,0] % 998244353
    p[:,1] = m[:,1] % 998244353
    p[:,2] = m[:,2] % 998244353
            
print(int(p[S,2]))

import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
 

m = np.zeros((S+1,3))
p = np.zeros((S+1,3))
p[0,0] = 1


for i in range(1,N+1):
    
    
    m[:,0] = p[:,0]
    m[:,1] = p[:,0] + p[:,1]  
    m[:,2] = p[:,0] + p[:,1] + p[:,2]  

    
    m[x[i-1]:,1] += p[:-x[i-1],0] + p[:-x[i-1],1]
    m[x[i-1]:,2] += p[:-x[i-1],0] + p[:-x[i-1],1]

    p[:,0] = m[:,0] % 998244353
    p[:,1] = m[:,1] % 998244353
    p[:,2] = m[:,2] % 998244353
            
print(int(p[S,2]))

Verdicts: Runtime Error

Accepted
Problem: Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.   For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:      * f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.  Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Submission attempts (in order):
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        ans += dp[S-a]*(N-i)
        dp[0] += 1
        for j in range(S-a-1, -1, -1):
            dp[j+a] += dp[j]
    print(ans % mod)

main()


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        dp[0] += i+1
        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        dp[0] +=1
        if a > S:
            continue

        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()


Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.   For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:      * f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.  Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Submission attempts (in order):
def setM():
    K2 = K // 2
    k = K // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m, ~m, (1 << K2 + k) % P))
        k //= 2

def modp(n):
    K2 = K // 2
    k = K // 2
    for k, m, tm, a in M:
        n = (n & tm) + (n & m >> K2 + k) * a
    return n

K = 64
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * 3001, 2)
mm = (1 << K * 3001) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += s >> S * K

print(ans % P)

K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = (1 << K * (S + 1)) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += s >> S * K

print(ans % P)

K = 32
P = 998244353
pa = (1 << 30) - ((1 << 30) % P)
M = []
N, S = map(int, input().split())
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = 1 << K * S
mmm = (1 << K) - 1
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += mm
    s += s >> a * K
    s -= ((s & m) >> 30) * pa
    ans += s & mmm

print(ans % P)

Verdicts: Wrong Answer

Wrong Answer

Runtime Error

Accepted
Problem: Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.   For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:      * f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.  Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Submission attempts (in order):
n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp1 = [[0] * (s + 1) for _ in range(n + 1)]
dp1[0][0] = 1

for i, e in enumerate(a, 1):
    for j in range(1, s + 1):
        if j - e >= 0:
            dp1[i][j] = dp1[i-1][j] + dp1[i-1][j-e]
        else:
            dp1[i][j] = dp1[i-1][j]

        dp1[i][j] %= mod

dp2 = [[0] * (s + 1) for _ in range(n + 1)]
dp2[0][0] = 1

for i, e in enumerate(a[::-1], 1):
    for j in range(1, s + 1):
        if j - e >= 0:
            dp2[i][j] = dp2[i - 1][j] + dp2[i - 1][j - e]
        else:
            dp2[i][j] = dp2[i - 1][j]

        dp2[i][j] %= mod

ans = 0
all = dp1[n][s]
for l in range(1, n + 1):
    for r in range(l, n + 1):
        cnt = all - dp1[l-1][s] - dp2[n-r][s]
        ans += cnt
        ans %= mod

print(ans)



import numpy as np

n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = np.zeros((s + 1, 3), dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()

    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.   For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:      * f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.  Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Submission attempts (in order):
import numpy as np

n,s = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
mod = 998244353


f = np.zeros(s+1)

for i in a:
    f[0] += 1
    f[i:] += f[:-i].copy()
    f %= mod
    ans += f[s]

print(ans)

import numpy as np

n,s = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
mod = 998244353


f = np.zeros(s+1,int)

for i in a:
    f[0] += 1
    f[i:] += f[:-i].copy()
    f %= mod
    ans += f[s]

print(ans%mod)

Verdicts: Wrong Answer

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
from itertools import count, repeat

h = int(input().split()[0])
a0 = repeat('.')
r0 = list(range(w))
for i in range(h):
  a = input()
  r = [i]
  for x, y, z, u in zip(a0, '.' + a, a, r0):
    r.append(min(u + (x + z == '.
  a0 = a
  r0 = r[1:]
print(r[-1])


from itertools import count, repeat

h = int(input().split()[0])
a0 = repeat('.')
r0 = count()
for i in range(h):
  a = input()
  r = [i]
  for x, y, z, u in zip(a0, '.' + a, a, r0):
    r.append(min(u + (x > z), r[-1] + (y > z)))
  a0 = a
  r0 = r[1:]
print(r[-1])


Verdicts: Runtime Error

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])
for x in grid:
  print(x)

# coding: utf-8
H, W = list(map(int, input().split()))
S = []
for _ in range(H):
    S.append(list(input()))

grid = [[0 for _ in range(W)] for _ in range(H)]

for h in range(1,H):
  if S[h-1][0] == '#' and S[h][0] == '.':
    grid[h][0] = grid[h-1][0] + 1
  else:
    grid[h][0] = grid[h-1][0]
    
for w in range(1,W):
  if S[0][w-1] == '#' and S[0][w] == '.':
    grid[0][w] = grid[0][w-1] + 1
  else:
    grid[0][w] = grid[0][w-1]
for w in range(1,W):
  for h in range(1,H):
    if S[h-1][w] == '#' and S[h][w] == '.':
      next_h = grid[h-1][w] + 1
    else:
      next_h = grid[h-1][w]      
    if S[h][w-1] == '#' and S[h][w] == '.':
      next_w = grid[h][w-1] + 1
    else:
      next_w = grid[h][w-1]
    grid[h][w] = min([next_w, next_h])
if S[H-1][W-1] == '#':
  grid[H-1][W-1] += 1
print(grid[H-1][W-1])

Verdicts: Wrong Answer

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
memory = [[-1 for i in range(W)] for j in range(H)]
def flip_count_mem(r, c):
  if memory[r][c] < 0:
    memory[r][c] = flip_coumt(r, c)
  return memory[r][c]

def flip_count (r, c):
  if r == H - 1 and c == W - 1:
    if s[r][c] == "#":
      return 1
    else:
      return 0
  
  if c == W - 1:
    count_right = 10000
  else:
    count_right = flip_count_mem (r, c + 1)
    if s[r][c] == "#" and s[r][c + 1] == ".":
      count_right += 1
  
  if r == H - 1:
    count_down = 10000
  else:
    count_down = flip_count_mem (r + 1, c)
    if s[r][c] == "#" and s[r + 1][c] == ".":
      count_down += 1
  return min(count_right, count_down)

H, W = input().split()
W = int (W)
H = int (H)
s = []
for i in range(H):
  s.append(input())
print (flip_count(0, 0))


def flip_count_mem(r, c):
  if memory[r][c] < 0:
    memory[r][c] = flip_count(r, c)
  return memory[r][c]

def flip_count (r, c):
  if r == H - 1 and c == W - 1:
    if s[r][c] == "#":
      return 1
    else:
      return 0
  
  if c == W - 1:
    count_right = 10000
  else:
    count_right = flip_count_mem (r, c + 1)
    if s[r][c] == "#" and s[r][c + 1] == ".":
      count_right += 1
  
  if r == H - 1:
    count_down = 10000
  else:
    count_down = flip_count_mem (r + 1, c)
    if s[r][c] == "#" and s[r + 1][c] == ".":
      count_down += 1
  return min(count_right, count_down)

H, W = input().split()
W = int (W)
H = int (H)
s = []
for i in range(H):
  s.append(input())
memory = [[-1 for i in range(W)] for j in range(H)]
print (flip_count(0, 0))


Verdicts: Runtime Error

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
import queue

H, W = map(int, input().split())

s = [list(map(int, input().split())) for _ in range(H)]

ini = 0
if s[0][0] == '#':
    ini = 1

dist = [[ini for _ in range(W)] for _ in range(H)]
start = (0,0)

qq = queue.Queue()

for i in range(H):
    for j in range(W):
        tgt = []
        if j == 0:
            pass
        else:
            if s[i][j-1] == '.' and s[i][j] == '#':
                tgt.append(dist[i][j-1] + 1)

            else:
                tgt.append(dist[i][j-1])

        if i == 0:
            pass
        else:
            if s[i-1][j] == '.' and s[i][j] == "#":
                tgt.append(dist[i-1][j] + 1)
            else:
                tgt.append(dist[i-1][j])
        if i + j == 0:
            continue
        dist[i][j] = min(tgt)

print(dist[H-1][W-1])



import queue

H, W = map(int, input().split())

s = [list(input()) for _ in range(H)]

ini = 0
if s[0][0] == '#':
    ini = 1

dist = [[ini for _ in range(W)] for _ in range(H)]
start = (0,0)

qq = queue.Queue()

for i in range(H):
    for j in range(W):
        tgt = []
        if j == 0:
            pass
        else:
            if s[i][j-1] == '.' and s[i][j] == '#':
                tgt.append(dist[i][j-1] + 1)

            else:
                tgt.append(dist[i][j-1])

        if i == 0:
            pass
        else:
            if s[i-1][j] == '.' and s[i][j] == "#":
                tgt.append(dist[i-1][j] + 1)
            else:
                tgt.append(dist[i-1][j])
        if i + j == 0:
            continue
        dist[i][j] = min(tgt)

print(dist[H-1][W-1])



Verdicts: Runtime Error

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    H,W = map(int,input().split())
    Gd = [list(input()) for _ in range(H)]
    INF = H*W
    direc = [[1,0],[0,1]]
    def dfs(start):
        Dis = [[INF]*W for _ in range(H)]
        Dis[start[0]][start[1]]= (Gd[start[0]][start[1]] == '#')
        q = deque([])   
        q.append(start)
        while len(q)!=0:
            h,w = q.popleft()   取りだし（先頭）
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if not (0<=hs<H and 0<=ws<W):
                    continue
                else:
                    q.append([hs,ws])
                    Dis[hs][ws] = min(Dis[hs][ws], Dis[h][w] + (Gd[hs][ws]=='#'))
        print(Dis[H-1][W-1])
    dfs([0, 0])

if __name__=='__main__':
    main()


#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    H, W = map(int,input().split())
    sth, stw = 0, 0
    glh, glw = H-1, W-1

    INF = 10000
    Gmap = [list(input()) for _ in range(H)]
    Dist = [[INF]*W for _ in range(H)]
    direc = {(1,0), (0,1)}

    if Gmap[0][0]=='#':
        Dist[0][0]=1
    else:
        Dist[0][0]=0

    for h in range(H):
        for w in range(W):
            nw = Gmap[h][w]
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if 0<=hs<H and 0<=ws<W:
                    cr = Gmap[hs][ws]
                    Dist[hs][ws] = min(Dist[hs][ws], Dist[h][w] + (cr=='#' and nw=='.'))
    print(Dist[glh][glw])

if __name__ == '__main__':
    main()

Verdicts: Time Limit Exceeded

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, w = na()
m = []
m = [ns() for _ in range(h)]
dp = [[inf] * w for _ in range(h)]
dp[0][0] = int(m[0][0] == '#')
for x in range(1, w):
    dp[0][x] = dp[0][x-1] + (int(m[0][x]=="#") if m[0][x-1]=="." else 0)
for y in range(1, h):
    dp[y][0] = dp[y-1][0] + (int(S[y][0]=="#") if S[y-1][0]=="." else 0)
    for x in range(1, W):
        dp[y][x] = min(
            dp[y][x-1] + (int(S[y][x]=="#") if S[y][x-1]=="." else 0),
            dp[y-1][x] + (int(S[y][x]=="#") if S[y-1][x]=="." else 0)
        )
print(dp[-1][-1])

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

h, w = na()
m = []
m = [ns() for _ in range(h)]
dp = [[inf] * w for _ in range(h)]
dp[0][0] = int(m[0][0] == '#')
for x in range(1, w):
    dp[0][x] = dp[0][x-1] + (int(m[0][x]=="#") if m[0][x-1]=="." else 0)
for y in range(1, h):
    dp[y][0] = dp[y-1][0] + (int(m[y][0]=="#") if m[y-1][0]=="." else 0)
    for x in range(1, w):
        dp[y][x] = min(
            dp[y][x-1] + (int(m[y][x]=="#") if m[y][x-1]=="." else 0),
            dp[y-1][x] + (int(m[y][x]=="#") if m[y-1][x]=="." else 0)
        )
print(dp[-1][-1])

Verdicts: Runtime Error

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = ['0' * (W+2)]
for _ in range(H):
    s.append('0' + input().rstrip() + '0')
s.append('0' * (W+2))

ans = []
if s[1][1] == '#': a = 1
else: a = 0
temp = [[1, 1, a]]

while temp:
    p = temp.pop()
    for y, x in [[p[0]+1, p[1]], [p[0], p[1]+1]]:
        if s[y][x] == '0':continue
        if s[y][x] == '#' and s[p[0]][p[1]] == '.':
            d = p[2] + 1
        if y == H and x == W:
            ans.append(d)
        else:
            temp.append([y, x, d])
            
print(min(ans))

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
s = [input().rstrip() for _ in range(H)]

dp = [[1000]*W for _ in range(H)]

if s[0][0] == '#': dp[0][0] = 1
else: dp[0][0] = 0

for j in range(W):
    for i in range(H):
        if i <= H - 2:

            if s[i][j] == '.' and s[i+1][j] == '#':
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + 1)
            else: dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if j <= W - 2:

            if s[i][j] == '.' and s[i][j+1] == '#':
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + 1)
            else: dp[i][j+1] = min(dp[i][j+1], dp[i][j])


print(dp[H-1][W-1])

Verdicts: Runtime Error

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
DP=[[201]*W for i in range(H)]
DP[0][0]=0
for y in range(H):
   for x in range(W):
      if x ==0 and y==0:
         DP[y][x] += 1 if l[y][x] == "#" else 0
         continue
      elif x == 0:
         DP[y][x] = DP[y-1][x]
      elif y == 0:
         DP[y][x] = DP[y][x-1]
      else:
         DP[y][x] = min(DP[y][x-1],DP[y-1][x])
      DP[y][x] += 1 if l[y][x] == "#" else 0
print(DP[H-1][W-1])
print(DP)

H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
inf=10**9
DP=[[inf]*W for i in range(H)]
DP[0][0]=0 if l[0][0]=="." else 1
for i in range(H):
   for j in range(W):
      if i>0:
         DP[i][j]=min(DP[i][j],DP[i-1][j]+1) if l[i-1][j] == "." and l[i][j]=="#" else min(DP[i][j],DP[i-1][j])
      if j>0:
         DP[i][j]=min(DP[i][j],DP[i][j-1]+1) if l[i][j-1] == "." and l[i][j]=="#" else min(DP[i][j],DP[i][j-1])
print(DP[H-1][W-1])

Verdicts: Wrong Answer

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
dp=[0]*W
if S[0][0]=='#':
  dp[0]=1
for j in range(1,W):
  if S[0][j]!=S[0][j-1]:
    dp[j]=dp[j-1]+1
  else:
    dp[j]=dp[j-1]

for i in range(1,H):
  print(dp)
  if S[i][0]!=S[i-1][0]:
    dp[0]=dp[0]+1
  for j in range(1,W):
    hidari=1 if S[i][j]!=S[i][j-1] and S[i][j-1]=='#' else 0
    ue=1 if S[i][j]!=S[i-1][j] and S[i-1][j]=='#' else 0
    dp[j]=min(dp[j-1]+hidari,dp[j]+ue)
print(dp)
print(dp[-1])

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
dp=[0]*W
if S[0][0]=='#':
  dp[0]=1
for j in range(1,W):
  if S[0][j]!=S[0][j-1] and S[0][j-1]=='.':
    dp[j]=dp[j-1]+1
  else:
    dp[j]=dp[j-1]
for i in range(1,H):
  if S[i][0]!=S[i-1][0] and S[i-1][0]=='.':
    dp[0]=dp[0]+1
  for j in range(1,W):
    hidari=1 if S[i][j]!=S[i][j-1] and S[i][j-1]=='.' else 0
    ue=1 if S[i][j]!=S[i-1][j] and S[i-1][j]=='.' else 0
    dp[j]=min(dp[j-1]+hidari,dp[j]+ue)
print(dp[-1])

Verdicts: Wrong Answer

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
import heapq
 
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())
    
visited=[[0]*w for _ in range(h)]
 
q=[(0,0,0)]
 
heapq.heapify(q)
visited=[[0]*w for _ in range(h)]
cnt=0
D=[[0]*w for _ in range(h)]
while q:
    cnt,px,py=heapq.heappop(q)
    D[px][py]=min(cnt,D[px][py])
    if  visited[px][py]==1:
        continue
    visited[px][py]=1

    for x,y in [(1,0),(0,1)]:
        if x+px>=h or y+py>=w:
            continue
        if S[px+x][py+y]!=S[px][py]:
            heapq.heappush(q,(cnt+1,px+x,py+y))
        else:
            heapq.heappush(q,(cnt,px+x,py+y))
if D[h-1][w-1]==0 and S[0][0]=='#':
    print(1)
else:
    print(D[h-1][w-1]+1//2)

h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())
    
cnt=0
D=[[10**9]*w for _ in range(h)]
D[0][0]=0
for i in range(h):
    for j in range(w):
        for x,y in [(0,1),(1,0)]:
            if i+x>=h or j+y>=w:
                continue
            if S[i][j]!=S[i+x][j+y]:
                D[i+x][j+y]=min(D[i][j]+1,D[i+x][j+y])
            else:
                D[i+x][j+y]=min(D[i][j],D[i+x][j+y])
                
                
if S[0][0]=='#':
    print(1+D[h-1][w-1]//2)
else:
    print(D[h-1][w-1]//2+(S[0][0]!=S[h-1][w-1]))

Verdicts: Wrong Answer

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
def flip_sq(sy, sx):
    gy = sy
    gx = sx
    while True:
        if sx == W - 1:
            if tiles[sy+1][sx] == "#":
                sy += 1
            else:
                break
        elif tiles[sy][sx+1] == "#":
            sx += 1
            if sy == H - 1:
                break
            if tiles[sy+1][sx] == "#":
                sy += 1
        else:
            break
    for y in range(gy, sy+1):
        for x in range(gx, sx+1):
            tiles[y][x] = flip[tiles[y][x]]

    print(tiles)

H, W = [int(i) for i in input().strip().split(" ")]
tiles = []
for i in range(H):
    tiles.append([i for i in input().strip()])

tile = {"#":1, ".":0}
flip = {"#":".", ".":"#"}
count = []
for i in range(H):
    count.append([])
    for j in range(W):
        count[i].append(0)

count[0][0] = tile[tiles[0][0]]
if tile[tiles[0][0]]:
    flip_sq(0, 0)

for y in range(H):
    for x in range(W):
        if y == 0:
            if x == 0:
                continue
            count[y][x] = count[y][x-1] + tile[tiles[y][x]]
        else:
            if x == 0:
                count[y][x] = count[y-1][x] + tile[tiles[y][x]]
            else:
                count[y][x] = min(count[y-1][x], count[y][x-1]) + tile[tiles[y][x]]
        if tile[tiles[y][x]]:
            flip_sq(y, x)

print(count[H-1][W-1])

H, W = map(int, input().split())
grid = [list(input().strip()) for _ in range(H)]

ans = [[0] * W for _ in range(H)]

if grid[0][0] == "#":
    ans[0][0] = 1

for i in range(H):
    for j in range(W):
        if i == 0 and j == 0:
            continue

        r = H*W
        d = H*W
        if j > 0 and grid[i][j] != grid[i][j-1] and grid[i][j-1] == ".":
            r = 1 + ans[i][j-1]
        elif j > 0:
            r = ans[i][j-1]

        if i > 0 and grid[i][j] != grid[i-1][j] and grid[i-1][j] == ".":
            d = 1 + ans[i-1][j]
        elif i > 0:
            d = ans[i-1][j]
        ans[i][j] = min(r, d)

print(ans[H-1][W-1])

Verdicts: Runtime Error

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
h,w=map(int,input().split())
li=[[]]*h
for i in range(h):
  li[i]=[str(k) for k in input()]
  
lil=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      if li[0][0]==".":
        lil[0][0]=0
      else:
        lil[0][0]=1
    elif i==0:
      if li[i][j]==li[i][j-1]:
        lil[i][j]=lil[i][j-1]
      else :
        lil[i][j]=lil[i][j-1]+1
    elif j==0:
      if li[i][j]==li[i-1][j]:
        lil[i][j]=lil[i-1][j]
      else:
        lil[i][j]=lil[i-1][j]+1
    else:
      if li[i][j]==li[i-1][j]:
        ko=lil[i-1][j]
      else:
        ko=lil[i-1][j]+1
      if li[i][j]==li[i][j-1]:
        ks=lil[i][j-1]
      else :
        ks=lil[i][j-1]+1
      lil[i][j]=min(ko,ks)
print(lil[h-1][w-1])    

h,w=map(int,input().split())
li=[[]]*h
for i in range(h):
  li[i]=[str(k) for k in input()]
  
lil=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  for j in range(w):
    if i==0 and j==0:
      if li[0][0]==".":
        lil[0][0]=0
      else:
        lil[0][0]=1
    elif i==0:
      if li[i][j]==li[i][j-1] or li[i][j]==".":
        lil[i][j]=lil[i][j-1]
      elif li[i][j]=="#":
        lil[i][j]=lil[i][j-1]+1
    elif j==0:
      if li[i][j]==li[i-1][j] or li[i][j]==".":
        lil[i][j]=lil[i-1][j]
      elif li[i][j]=="#":
        lil[i][j]=lil[i-1][j]+1
    else:
      if li[i][j]==li[i-1][j] or li[i][j]==".":
        ko=lil[i-1][j]
      elif li[i][j]=="#":
        ko=lil[i-1][j]+1
      if li[i][j]==li[i][j-1] or li[i][j]==".":
        ks=lil[i][j-1]
      elif li[i][j]=="#":
        ks=lil[i][j-1]+1
      lil[i][j]=min(ko,ks)
print(lil[h-1][w-1])  

Verdicts: Wrong Answer

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
import copy
H, W = map(int, input().split())
s = [[0] * W]
minus = 0
tmp = [list(input()) for _ in range(H)]
for i in range(H):
    s.append(tmp[i])
if s[1][0] == '#':
    minus = 1
    for i in range(W):
        s[0][i] = 1
else:
    s[0][0] = 0

scopy = copy.deepcopy(s)
for i in range(1, H + 1):
    for j in range(W):
        if s[i][j] == '#':
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + 1
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + 1, s[i][j - 1] + 1)
            else:
                s[i][j] = s[i - 1][j] + 1
            for k in range(i, H + 1):
                if k == i:
                    for l in range(j, W):
                        if l == j: continue
                        if s[k][l] != '.':
                            s[k][l] = s[i][j]
                        else:
                            break
                else:
                    if s[k][j] != '.':
                        s[k][j] = s[i][j]
                    else:
                        break
        elif s[i][j] == '.':
            index = 0
            if scopy[i][j] == '#':
                index += 1
            if j != 0 and i == 1:
                s[i][j] = s[i][j - 1] + index
            elif j != 0:
                s[i][j] = min(s[i - 1][j] + index, s[i][j - 1] + index)
            else:
                s[i][j] = s[i - 1][j] + index
print(s)
print(s[-1][-1] - minus)


INF = 10 ** 9
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[INF for _ in range(W)] for _ in range(H)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if j != 0:
            cnt = 0
            if s[i][j] == '#' and s[i][j - 1] == '.':
                cnt += 1
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + cnt)

        if i != 0:
            cnt = 0
            if s[i][j] == '#' and s[i - 1][j] == '.':
                cnt += 1
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + cnt)

print(dp[-1][-1])

Verdicts: Wrong Answer

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
def main():
    h,w = map(int, input().split())
    s = []
    for i in range(h):
        ss = list(input())
        s.append(ss)

    now = [0,0]
    cnt = 0
    if s[0][0] == '#':
        cnt += 1
        # s[0][0] = '.'
    if s[h-1][w-1] == '#':
        # cnt += 1
        # s[h-1][w-1] = '.'

    dp = [[-1] * w for i in range(h)]
    dp[0][0] = cnt

    for i in range(h):
        for j in range(w):
            tmp_up = 100000
            tmp_left = 100000
            change  = 0
            if s[i][j] == '#':
                change = 1
            if i == 0 and j == 0:
                continue
            if i != 0:
                if s[i-1][j] == '#' and s[i][j] == '#':
                    tmp_up = dp[i-1][j]
                else:
                    tmp_up = dp[i-1][j] + change
            if j != 0:
                if s[i][j-1] == '#' and s[i][j] == '#':
                    tmp_left = dp[i][j-1]
                else:

                    tmp_left = dp[i][j-1] + change

            dp[i][j] = min(tmp_up,tmp_left)


    print(dp[h-1][w-1])
    print(dp)

if __name__ == '__main__':
    main()


def main():
    h,w = map(int, input().split())
    s = []
    for i in range(h):
        ss = list(input())
        s.append(ss)

    now = [0,0]
    cnt = 0
    if s[0][0] == '#':
        cnt += 1
        # s[0][0] = '.'
    

    dp = [[-1] * w for i in range(h)]
    dp[0][0] = cnt

    for i in range(h):
        for j in range(w):
            tmp_up = 100000
            tmp_left = 100000
            change  = 0
            if s[i][j] == '#':
                change = 1
            if i == 0 and j == 0:
                continue
            if i != 0:
                if s[i-1][j] == '#' and s[i][j] == '#':
                    tmp_up = dp[i-1][j]
                else:
                    tmp_up = dp[i-1][j] + change
            if j != 0:
                if s[i][j-1] == '#' and s[i][j] == '#':
                    tmp_left = dp[i][j-1]
                else:

                    tmp_left = dp[i][j-1] + change

            dp[i][j] = min(tmp_up,tmp_left)


    print(dp[h-1][w-1])

if __name__ == '__main__':
    main()


Verdicts: Runtime Error

Accepted
Problem: Consider a grid with H rows and W columns of squares. Let (r, c) denote the square at the r-th row from the top and the c-th column from the left. Each square is painted black or white.  The grid is said to be _good_ if and only if the following condition is satisfied:    * From (1, 1), we can reach (H, W) by moving one square **right or down** repeatedly, while always being on a white square.  Note that (1, 1) and (H, W) must be white if the grid is good.  Your task is to make the grid good by repeating the operation below. Find the minimum number of operations needed to complete the task. It can be proved that you can always complete the task in a finite number of operations.    * Choose four integers r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W). For each pair r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1), invert the color of (r, c) \- that is, from white to black and vice versa.

Submission attempts (in order):
H,W=map(int,input().split())

dp = [[0 for i in range(W)] for j in range(H)]

arr = []
for h in range(H):
  s = list(input())
  arr.append(s)

if arr[0][0] == "#":
  dp[0][0] = 1
  
for h in range(H):
  for w in range(W):
    if h == 0:
      if w != 0:
        a = arr[h][w]
        b = arr[h][w-1]
        if a == b or a == ".":
          dp[h][w] = dp[h][w-1]
        else:
          dp[h][w] = dp[h][w-1] + 1
 
    else:      
      if w == 0:
        a = arr[h][w]
        b = arr[h-1][w]
        if  a == b or a == ".":
          dp[h][w] = dp[h-1][w]
        else:
          dp[h][w] = dp[h-1][w] + 1

      else:
        a = arr[h][w] 
        b = arr[h][w-1]
        c = arr[h-1][w]
        if a == b or a == "." or a == c:
          dp[h][w] = min(dp[h][w-1],dp[h-1][w])
        else:
          dp[h][w] = min(dp[h][w-1] + 1,dp[h-1][w]+1)
    
print(dp[H-1][W-1])

H,W=map(int,input().split())

dp = [[0 for i in range(W)] for j in range(H)]

arr = []
for h in range(H):
  s = list(input())
  arr.append(s)

if arr[0][0] == "#":
  dp[0][0] = 1
  
for h in range(H):
  for w in range(W):
    if h == 0:
      if w != 0:
        a = arr[h][w]
        b = arr[h][w-1]
        if a == b or a == ".":
          dp[h][w] = dp[h][w-1]
        else:
          dp[h][w] = dp[h][w-1] + 1
 
    else:      
      if w == 0:
        a = arr[h][w]
        b = arr[h-1][w]
        if  a == b or a == ".":
          dp[h][w] = dp[h-1][w]
        else:
          dp[h][w] = dp[h-1][w] + 1

      else:
        a = arr[h][w] 
        b = arr[h][w-1]
        c = arr[h-1][w]
        if a == "." or (a == b and a == c):
          dp[h][w] = min(dp[h][w-1],dp[h-1][w])
        elif a == b:
          dp[h][w] = dp[h][w-1]
        elif a == c:
          dp[h][w] = dp[h-1][w]
        else:
          dp[h][w] = min(dp[h][w-1] + 1,dp[h-1][w]+1)
    
print(dp[H-1][W-1])

Verdicts: Wrong Answer

Accepted