滅鼠先鋒編程題目及答案【題目】在一個農(nóng)場里，老鼠猖獗，農(nóng)場主決定雇傭滅鼠先鋒來消滅老鼠。農(nóng)場主給滅鼠先鋒提供了一個農(nóng)場的地圖，地圖上用一個二維數(shù)組表示，其中0表示空地，1表示老鼠。滅鼠先鋒需要在地圖上移動，每次只能向上、下、左、右四個方向之一移動。滅鼠先鋒的目標是消滅所有的老鼠，并且盡可能少地移動步數(shù)。請編寫一個程序，計算滅鼠先鋒消滅所有老鼠所需的最少步數(shù)。【輸入】輸入包含多行，第一行為兩個整數(shù)n和m（1≤n,m≤100），表示農(nóng)場地圖的行數(shù)和列數(shù)。接下來的n行，每行包含m個整數(shù)，表示農(nóng)場地圖的每個位置的狀態(tài)?！据敵觥枯敵鲆粋€整數(shù)，表示滅鼠先鋒消滅所有老鼠所需的最少步數(shù)?！臼纠枯斎耄?3010001010輸出：4【答案】```pythonfromcollectionsimportdequedefmin_steps_to_kill_all_rats(n,m,grid):定義方向directions=[(0,1),(1,0),(0,-1),(-1,0)]標記已經(jīng)訪問過的位置visited=[[False]mfor_inrange(n)]使用隊列進行廣度優(yōu)先搜索queue=deque()初始化隊列，將所有老鼠的位置加入隊列foriinrange(n):forjinrange(m):ifgrid[i][j]==1:queue.append((i,j,0))(x,y,steps)visited[i][j]=True廣度優(yōu)先搜索whilequeue:x,y,steps=queue.popleft()如果所有老鼠都被消滅，返回步數(shù)ifall(all(cell==0forcellinrow)forrowingrid):returnsteps遍歷四個方向fordx,dyindirections:nx,ny=x+dx,y+dy檢查新位置是否在地圖內(nèi)，并且沒有訪問過if0<=nx<nand0<=ny<mandnotvisited[nx][ny]andgrid[nx][ny]==1:queue.append((nx,ny,steps+1))visited[nx][ny]=True讀取輸入n,m=map(int,input().split())grid=[list(map(int,input().split()))for_inrange(n)]計算最少步數(shù)result=min_steps_to_kill_all_rats(n,m,grid)輸出結(jié)果print(result)```【分析】本題是一個基于廣度優(yōu)先搜索（BFS）的算法問題。我們需要從每個老鼠的位置開始，逐個消滅老鼠，同時記錄消滅所有老鼠所需的最少步數(shù)。我們使用隊列來存儲待處理的位置