fjf17391520224 @ 2024-03-30 10:28:07
package dfs;
import java.util.Scanner;
public class test1 {
static int n;
static Scanner sc=new Scanner(System.in);
static int [][]a;
static int [][]vis;
static int [][]q;
static int []dx={0,0,-1,1};
static int []dy= {-1,1,0,0};
static int min;
public static void main(String[] args) {
n=sc.nextInt();
a=new int[n][n];
vis=new int [n][n];
q=new int [n*n][2];//static 先声明后创建
for (int i = 0; i <n; i++) {
String s=sc.next();
for (int j = 0; j <n; j++) {
a[i][j]=s.charAt(j)-'0';
}
}
int s1=sc.nextInt();
int s2=sc.nextInt();
int s3=sc.nextInt();
int s4=sc.nextInt();
bfs(s1-1,s2-1,s3-1,s4-1);
}
private static void bfs(int x1, int y1, int x2, int y2) {
int r=0,h=0;
q[r][0]=x1;
q[r][1]=y1;
vis[x1][y1]=1;
r++;
//先入队做好标记,队不为空时对每层元素处理,终止条件看当前队头元素是否到达终点,然后队头元素扩展(符合条件入队),队头元素出队(扩展完后)
while (r-h>0) {
for (int j = 0; j <r-h; j++) {
if(q[h][0]==x2&&q[h][1]==y2) {
System.out.println(min);
return;
}
for (int i = 0; i <4; i++) {
int nx=q[h][0]+dx[i];
int ny=q[h][1]+dy[i];
if(nx<0||nx>=n||ny<0||ny>=n) {//注意判断条件 先判断那些,再判断数组vis a
continue;
}
if(a[nx][ny]==1||vis[nx][ny]==1) {
continue;
}
vis[nx][ny]=1;
q[r][0]=nx;
q[r][1]=ny;
r++;
min++;
}
h++;
}
}
}
}