鲁康华


私信TA

用户名:uq_32497986585

访问量:1018

签 名:

我菠萝吹雪浪迹一生 最幸福的时候就是梨花诗说愿意的...

等  级
排  名 2639
经  验 2097
参赛次数 1
文章发表 10
年  龄 0
在职情况 学生
学  校 鄂州职业大学
专  业

  自我简介:

我菠萝吹雪 行走江湖多年 原本打算封心锁爱 没想到看到你还是会心动 我的梨花诗

解题思路:


1、整个对象类把我们需要的x,y ,step,也就是行列步数

其实也就是我们的bfs模板而已,基本都大差不差。


2、记得用LinkedList,因为LinkedList虽然类似于 ArrayList,

但是与 ArrayList 相比,LinkedList 的增加和删除的操作效率更高,

而查找和修改的操作效率比较低,结合我们的题目所以我认为使用LinkedList比较好。


3、这里我们不是在输入吗,那就一行一行的来,找到S就记录下来,我理解的是S就是我们的入口,E就是我们的出口

然后我们可以把他放入我们的LinkedList。


4、这个时候就可以用到我们的vis boolean 数组了,用来判断我们有没有走过这条路,没有就继续BFS,否则就换个路,

别忘了把我们当前使用的对象取出来,删除掉,队列不删除怎么用后面的呢,不要搞麻烦了。


欢迎点评


参考代码:

package BFS;

import java.util.LinkedList;
import java.util.Scanner;

public class S_迷宫问题 {
	static class node{
		int x,y,step;
		node(int x,int y,int step){
			this.x = x;
			this.y = y;
			this.step = step;
		}
	}
	static LinkedList<node> list = new LinkedList<>();
	static int[]dx = {-1,0,1,0};
	static int[]dy = {0,1,0,-1};
	static int n,m,x,y;
	static boolean [][] vis = new boolean [205][205];
	static char [][]g = new char[205][205];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i = 0;i < t;i ++) {
			n = sc.nextInt();
			m = sc.nextInt();
			for(int j = 0;j < n;j ++) {
				String s = sc.next();
				g[j] = s.toCharArray();
				for(int k = 0;k < m;k ++) {
					if(g[j][k] == 'S') {
						x = j;
						y = k;
					}
				}
			}
			int ans = bfs();
			if (ans == -1) {
				System.out.println("oop!");
			}else {
				System.out.println(ans);
			}
		}
	}
	 static int bfs() {
		while (!list.isEmpty()) {
			list.pollFirst();
		}
		for(int i = 0;i < n;i ++) {
			for(int j = 0;j < m;j ++) {
				vis[i][j] = false;
			}
		}
		list.add(new node(x,y,0));
		
		while (!list.isEmpty()) {
			node cur = list.pollFirst();
			if (g[cur.x][cur.y] == 'E') {
				return cur.step;
			}
			for (int i = 0; i < 4; i++) {
				int a = cur.x + dx[i];
				int b = cur.y + dy[i];
				if (a >= 0 && a < n && b >= 0 && b < m && g[a][b]!='#' && !vis[a][b]) {
					vis[a][b]=true;
					list.add(new node(a,b,cur.step+1));
				}
			}
		}
		return -1;
	}
}


 

0.0分

3 人评分

  评论区