java代码手搓队列,eclipse可以过,洛谷过不了
查看原帖
java代码手搓队列,eclipse可以过,洛谷过不了
1205731
fjf17391520224楼主2024/3/30 10:28
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++;
			}
		}
	
}
}

2024/3/30 10:28
加载中...