bfs類的應用題。

解法：

每一個點都可能作為匯集的那個點，因此采用遍歷的方式，對每個點進行處理，得出每個點的“所有馬跳到本點的最小步數和“，取最小值即可。

邏輯1：以該點作為源點出發，求處從該點出發訪問所有馬（如果能訪問完）所需的最小步數。根據馬走日的規則，下一步有八個格子可作為”下一個格子“，”下一個格子“可能是馬，也有可能是空格。

如果是馬，該馬有自己的可跳距離k，從該馬的位置離源點的步數step（暗示用隊列）已知，若k>=step,說明該馬可跳到匯集點（源點），否則結束，因為有一個馬無法跳到匯集點；

如果是空格，該空格可能作為馬到匯集點的一個中轉點。

邏輯2：不管下一個格是馬還是空格，從該位置到匯集點的最小步數是動態更新的（同親子游戲，或從示例演算得出），因此需要為該位置維護一個動態值，使用二維數組完成。此外，對于每個點，其下一步所到達的格子是確定的（按規則走，最多8格），所以每個點至多加入隊列一次，重復加入無意義（因為該點到源點的最小步數是動態維護的）且會爆內存。

代碼

import java.util.*;
public class Main{public static void main(String[] args){Scanner in=new Scanner(System.in);String[] size=in.nextLine().split(" ");int m=Integer.parseInt(size[0]),n=Integer.parseInt(size[1]);char [][] board=new char[m][n];// 馬的個數int count=0;for(int i=0;i<m;i++){String s=in.nextLine();for(int j=0;j<n;j++){board[i][j]=s.charAt(j);if(board[i][j]!='.'){count++;}}}//以每一個“馬”出發，在所有馬限定的步數board[i][j]下，感染完所有馬所需的最小步數h，取h的最小值// bfs搜索int[][] arr=new int[][]{{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};int ans=Integer.MAX_VALUE;for(int i=0;i<m;i++){for(int j=0;j<n;j++){//record[i][j]:從點（i，j）處到源點（i0，j0）處所需的最小步數int[][] record=new int[m][n],used=new int[m][n];Deque<int[]> queue=new ArrayDeque<>();queue.add(new int[]{i,j});// cnt：可跳到源點處的馬的數量int cnt=0;while(!queue.isEmpty()){int[] cur=queue.poll();int row=cur[0],col=cur[1],step=record[row][col];//防止回訪used[row][col]=1;// 下一跳檢查for(int[] a:arr){int nr=row+a[0],nc=col+a[1];if(nr<0||nr>=m||nc<0||nc>=n||used[nr][nc]==1){continue;}if((board[nr][nc]!='.'&&(board[nr][nc]-'0')>=step+1)||(board[nr][nc]=='.')){if(record[nr][nc]==0){if(board[nr][nc]!='.'){cnt++;}//step+1是最小值record[nr][nc]=step+1;//繼續搜索queue.add(new int[]{nr,nc});}else{//更新值即可record[nr][nc]=Math.min(record[nr][nc],step+1);}}}}//維護最小步數和ansint sum=0,copy=count-1;if(board[i][j]=='.'){copy=count;}if(cnt==copy){for(int r=0;r<m;r++){for(int c=0;c<n;c++){if(board[r][c]!='.'){sum+=record[r][c];}}}ans=Math.min(ans,sum);}}}System.out.println(ans==Integer.MAX_VALUE?-1:ans);}
}