Java error在洛谷做题，我想问一下哪里错误了？

来源：蜘蛛抓取(WebSpider) 时间：2023-11-05 11:01 标签： Java error
题目描述有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上，那么你可以移动到相邻4格中的某一格1上，同样若你位于一格1上，那么你可以移动到相邻4格中的某一格0上。你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。输入格式第1行为两个正整数n,m。下面n行，每行n个字符，字符只可能是0或者1，字符之间没有空格。接下来m行，每行2个用空格分隔的正整数i,j，对应了迷宫中第i行第j列的一个格子，询问从这一格开始能移动到多少格。输出格式m行，对于每个询问输出相应答案。输入
2 201101 12 2
输出
44
算法思路（记忆化搜索，联通块）0只能到1，1只能到0，因此判断条件可以判断两点是否相同。思路一：没输入一个点，直接BFS搜索答案，当数据量大时，内存超限，因此创建太多的queue，栈溢出。思路二：（联通块）给出01图，直接遍历每个点，判断每个点所能到达的位置。当两个点互通，则两个点经过的点数一定相同，因此找到某一块的最大经过点数，则这一块所有经过点数都相同。另外加上 vis 数组记忆化搜索，避免重复搜索。最终得到每一个点的最大搜索数，存入结果数组中，最后根据输入点，直接输出结果，减少重复BFS的次数。BFS错误示范思路一：BFS暴力import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int cnt = 0;
static int[] orient = {0, 1, 0, -1, 0};
static boolean[][] vis;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
char[][] x = new char[n][n];
for (int i = 0; i < n; i++) {
x[i] = sc.next().toCharArray();
}
Queue<int[]> queue = new LinkedList<>();
while (m-- > 0) {
cnt = 1;
vis = new boolean[n][n];
queue.clear();
int i = sc.nextInt()-1;
int j = sc.nextInt()-1;
queue.offer(new int[]{i, j});
vis[i][j] = true;
while (!queue.isEmpty()) {
int[] loc = queue.poll();
for (int k = 0; k < 4; k++) {
i = loc[0] + orient[k];
j = loc[1] + orient[k+1];
if (i < 0
j < 0
i >= x.length
j >= x.length
vis[i][j]
x[loc[0]][loc[1]] == x[i][j])
continue;
cnt++;
vis[i][j] = true;
queue.offer(new int[]{i, j});
}
}
System.out.println(cnt);
}
}
}
DFS错误示范DFS需要更多的栈空间，因此该题直接不考虑，下面代码有bug，后来也就没有改了，直接研究BFS了。import java.util.Scanner;
public class Main {
static int cnt = 0;
static int[] orient = {0, 1, 0, -1, 0};
static boolean[][] vis;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
char[][] x = new char[n][n];
for (int i = 0; i < n; i++) {
x[i] = sc.next().toCharArray();
}
while (m-- > 0) {
int i = sc.nextInt();
int j = sc.nextInt();
cnt = 0;
vis = new boolean[n][n];
dfs(x,i-1, j-1);
System.out.println(cnt);
}
}
public static void dfs(char[][] x, int i, int j) {
if (i < 0
j < 0
i >= x.length
j >= x.length
vis[i][j])
return;
vis[i][j] = true;
cnt++;
if (x[i][j] == '0') {
for (int k = 0; k < 4; k++) {
dfs(x, i+orient[k], j+orient[k+1]);
}
} else {
for (int k = 0; k < 4; k++) {
int ii = i + orient[k];
int jj = j + orient[k+1];
if (ii < 0
jj < 0
ii >= x.length
jj >= x.length
vis[ii][jj])
continue;
else
dfs(x, ii, jj);
}
}
}
}
BFS优化如果不加快速输入输出，仍然和上面一样内存超限，加上快输就AK了。import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
static int[] orient = {0, 1, 0, -1, 0};
static boolean[][] vis;
public static void main(String[] args) {
myScanner sc = new myScanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
char[][] x = new char[n][];
for (int i = 0; i < n; i++) {
x[i] = sc.next().toCharArray();
}
int[][] res = new int[n][n];
Queue<int[]> queue = new LinkedList<>();
Queue<int[]> queue2 = new LinkedList<>();
vis = new boolean[n][n];
for (int k = 0; k < n; k++) {
for (int p = 0; p < n; p++) {
if (!vis[k][p]) {
vis[k][p] = true;
queue.add(new int[]{k, p});
queue2.add(new int[]{k, p});
int sum = 0;
while (!queue.isEmpty()) {
sum++;
int[] loc = queue.poll();
for (int l = 0; l < 4; l++) {
int i = loc[0] + orient[l];
int j = loc[1] + orient[l + 1];
if (i < 0
j < 0
i >= x.length
j >= x.length
vis[i][j]
x[loc[0]][loc[1]] == x[i][j])
continue;
vis[i][j] = true;
queue.offer(new int[]{i, j});
queue2.offer(new int[]{i, j});
}
}
while (!queue2.isEmpty()) {
int[] loc = queue2.poll();
res[loc[0]][loc[1]] = sum;
}
}
}
}
while (m-- > 0) {
int i = sc.nextInt()-1;
int j = sc.nextInt()-1;
System.out.println(res[i][j]);
}
}
// 优化输入
static class myScanner {
public BufferedReader reader;
public StringTokenizer st;
myScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
st = null;
}
public int nextInt() {
return Integer.parseInt(next());
}
public String next() {
while (st == null
!st.hasMoreTokens()) {
try {
st = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
}
}
加油!感谢!努力!

我要回帖

更多关于 Java error 的文章

 

随机推荐