給定一個n*m的二維整數陣列，用來表示一個迷宮，陣列中只包含0或1，其中0表示可以走的路，1表示不可通過的墻壁，
最初，有一個人位于左上角(1, 1)處，已知該人每次可以向上、下、左、右任意一個方向移動一個位置，
請問，該人從左上角移動至右下角(n, m)處，至少需要移動多少次，
資料保證(1, 1)處和(n, m)處的數字為0，且一定至少存在一條通路，
輸入格式
第一行包含兩個整數n和m，
接下來n行，每行包含m個整數（0或1），表示完整的二維陣列迷宮，
輸出格式
輸出一個整數，表示從左上角移動至右下角的最少移動次數，
資料范圍
1≤n,m≤1001≤n,m≤100
輸入樣例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
輸出樣例：
8
bfs一般用于求最短路徑/最少次數這種問題，每個狀態的變化權值必須一樣
代碼：import java.util.ArrayDeque; import java.util.Scanner; class Node{ int x; int y; int step; public Node(int x,int y,int step){ this.x=x; this.y=y; this.step=step; } } public class Main{ static final int N=105; static int n,m; static int map[][]=new int[N][N]; static int dx[]={1,-1,0,0}; static int dy[]={0,0,1,-1}; static ArrayDeque<Node> q=new ArrayDeque<>(); static void bfs(){ q.offer(new Node(0,0,0)); while(!q.isEmpty()){ Node t=q.poll(); if(t.x==n-1 && t.y==m-1){ System.out.println(t.step); break; } for(int i=0;i<4;i++){ int xx=t.x+dx[i]; int yy=t.y+dy[i]; if(xx<0 || yy<0 || xx>=n || yy>=m || map[xx][yy]==1) continue; map[xx][yy]=1; q.offer(new Node(xx,yy,t.step+1)); } } } public static void main(String[] args) { Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) map[i][j]=scan.nextInt(); bfs(); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/98390.html
標籤：其他