java代码手搓队列,eclipse可以过,洛谷过不了

P1746 离开中山路

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++;
            }
        }

}
}

|