[問題解決]バージン-7576トマト(dfs&bfs)

提问链接

問題の説明

チョルスのトマト農場にはトマトを保管する大きな倉庫がある.トマトは下図のように1つずつ四角い格子に入れて倉庫に保管しています.

倉庫に保管されているトマトの中には、熟しているものもあれば、まだ熟していないものもあります.1日保管した後、熟したトマトに隣接する未熟のトマトは、熟したトマトの影響を受けて成熟する.1つのトマトの隣接する場所は、左、右、前、後の4つの方向に位置するトマトを意味する.対角線方向に影響を与えないトマトは、トマトが自分で成熟しないと仮定します.哲洙は倉庫に保管されているトマトが何日で熟れるか、最低日数を知りたいと思っている.
倉庫にトマトのチェックボックスの大きさ、熟したトマトと未熟なトマトの情報を保管している場合、数日後には、トマトが熟しているかどうか、最低日数を求めるプログラムを作成します.しかし、箱のいくつかの格にはトマトが入っていないかもしれません.

入力

最初の行は、ボックスのサイズを表す2つの整数M,Nを与える.Mは箱の横格子数,Nは箱の縦格子数を表す.しかし,2≦M,N≦1000であった.2行目から、1つの箱に保存されているトマトの情報が提供されます.つまり、2行目からN行目まで、箱の中のトマトの情報が出てきます.1本の線上で、箱の横線のトマトの状態はM個の整数である.整数1は熟したトマトを表し、整数0は未熟のトマトを表し、整数-1はトマトを含まない格子を表す.
トマトが1つ以上ある場合にのみ入力します.

しゅつりょく

トマトがすべて熟成した最小日付を印刷します.保存からすべてのトマトが熟成している場合は0を、トマトが熟成していない場合は-1を出力します.

入力例1

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

サンプル出力1

8

入力例2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

サンプル出力2

-1

入力例3

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

サンプル出力3

6

入力例4

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

サンプル出力4

14

入力例5

2 2
1 -1
-1 1

サンプル出力5

0

私の答え

隣接ノードの検索と最短日付を求める部分にbfsを適用すべきだと思います.
熟成したトマトでナビゲーションを開始し、図[i][j]=1の場合はキューに位置を置く.
未熟トマトであればgraph[nx][ny]=graph[x][y]+1で閲覧回数を積算し、最後に総閲覧回数を比較してcntに保存し、cnt-1を出力する.

917パーセントの標準スコアのエラーの回答(残りのコードは同じ)

def solution():
    answer =True
    for i in range(m):
        for j in range(n):
            if graph[i][j] ==0:
                print(-1)
                answer = False
                break
        break
        
    if answer:
        cnt = 0
        for i in range(m):
            for j in range(n):
                cnt = max(graph[i][j], cnt)          
        print(cnt-1)

👉 反例
最初の反例は予想とは異なりbreakを用いた.完熟トマトが存在する場合は、反復ドア全体から脱出しようとしますが、外側の反復ドアが内側の反復ドアを回ってから脱出するように設計されています.下;

3 3
1 1 0 
-1 -1 -1
-1 -1 0   -> 1 (답 -1)

2 2
1 -1
-1 1 (답 0)

修正の解答

def solution():
    answer =True
    for i in range(m):
        for j in range(n):
            if graph[i][j] ==0:
                print(-1)
                answer = False
                break
        if answer == False:
        break
                
    if answer:
        cnt = 0
        for i in range(m):
            for j in range(n):
                cnt = max(graph[i][j], cnt)          
        print(cnt-1)            

ブレークポイントに条件を付け、コードを変更して終了させます.
2番目のクラスでは、熟していないトマトをあげない場合もあります.最小日付は最後に問題を解決した.
2つのコードをパブリッシュします.
コード1は700 ms、クイックコードは350 ms程度必要です.

コード#コード#

マイコード

from collections import deque
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
graph = [list(map(int,  input().split())) for _ in range(m)]
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    global queue
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx and nx<m and 0<=ny and ny<n :
                if graph[nx][ny] == 0 :
                    graph[nx][ny] = graph[x][y] + 1
                    queue.append([nx, ny])

for i in range(m):
    for j in range(n):
        if graph[i][j] == 1:
            queue.append([i, j]) 

bfs() 
answer =True
for i in range(m):
    for j in range(n):
        if graph[i][j] ==0:
            print(-1)
            answer = False
            break
    if answer == False:
        break
if answer:
    cnt = 0
    for i in range(m):
        for j in range(n): # 처음부터 안익은 토마토가 0개인 반례를 고려하여 최댓값을 마지막에 구하도록 함
            cnt = max(graph[i][j], cnt)          
    print(cnt-1) # bfs 시작한 지점이 썩은 토마토이고, 이값을 반영해서 cnt를 구했기 때문에 더해진 1을 뺸다.

クイックコード

# 빠른 풀이
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
move = ((1,0),(0,1),(-1,0),(0,-1))
queue = []
nextqueue = []
board = []
ans = 0
for i in range(m):
    temp = list(map(int,input().split()))
    for j,k in enumerate(temp):
        if k == 1:
            queue.append((i,j))
    board.append(temp)
while len(queue):
    for x,y in queue:
        for dx,dy in move:
            if 0 <= x+dx < m and 0 <= y+dy < n:
                if board[x+dx][y+dy] == 0:
                    nextqueue.append((dx+x,dy+y))
                    board[x+dx][y+dy] = 1
    ans += 1
    queue = nextqueue
    nextqueue = []
if all(list(map(all,board))):
    print(ans-1)
else:
    print(-1)