글 읽기 - 1890, BFS로 풀어봤습니다. 반례 부탁드립니다.

hyunbo 3년 전 0

테스트 케이스는 통과 하는데 반례를 못 찾겠네요.

반례 찾아주시면 감사하겠습니다.

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

N = int(input())

matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))

memo = [[0] * N for _ in range(N)]
memo[0][0] = 1

q = deque()

q.append((0,0))
while q:
    i, j = q.popleft()
    num = matrix[i][j]
    if num == 0:
        continue

    if i + num < N :
        if memo[i + num][j] == 0:
            q.append((i+num, j))
        memo[i+num][j] += memo[i][j]

    if j + num < N:
        if memo[i][j + num] == 0:
            q.append((i, j+num))
        memo[i][j+num] += memo[i][j]

print(memo[N-1][N-1])

qjatn1009 3년 전 4

3 1 2 2 3 3 1 1 2

1 1 2 1 1 2 3 1 2

2 1 1 3 2 2 1 3 1

3 3 1 1 1 3 1 2 1

3 2 2 2 1 1 3 3 1

3 1 3 2 2 3 1 3 3

3 1 1 2 1 1 1 1 1

2 3 1 3 1 3 2 2 2

3 3 3 2 3 1 3 3 0

answer : 6

출력 : 2

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1890, BFS로 풀어봤습니다. 반례 부탁드립니다.

hyunbo 3년 전 0

qjatn1009 3년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말