题目描述
blablabla
样例
import java.util.*;
class Node{
int x;
int y;
public Node(int x,int y){
this.x = x;
this.y =y;
}
}
class Main{
static Scanner sc =new Scanner(System.in);
static int n =sc.nextInt();
static int m =sc.nextInt();
static int[][] arr = new int[100][100];//地图
static int[][] d =new int[100][100];//到起始点的距离
public static int dfs(){
Queue<Node>q =new LinkedList<>();
//搞向量,上下左右走
int[] dx = {0,1,0,-1};
int[] dy = {1,0,-1,0};
q.add(new Node(0,0));
while(!q.isEmpty()){
Node head = q.poll();
if(head.x==n-1&&head.y==m-1){
break;
}
for(int i =0;i<4;i++){
int newx =head.x+dx[i];
int newy =head.y+dy[i];
if(newx>=0&&newx<n&&newy>=0&&newy<m&&arr[newx][newy]==0&&d[newx][newy]==0){
q.add(new Node(newx,newy));
d[newx][newy] = d[head.x][head.y]+1;
}
}
}
return d[n-1][m-1];
}
public static void main(String[] args){
for(int i =0;i<n;i++){
for(int j = 0;j<m;j++){
arr[i][j] = sc.nextInt();
}
}
System.out.println(dfs());
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla