解题思路:
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 人评分
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:742 |
兰顿蚂蚁 (C++代码)浏览:1212 |
printf基础练习2 (C语言代码)浏览:952 |
IP判断 (C语言代码)浏览:816 |
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:541 |
1017题解浏览:661 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:707 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:753 |
C语言程序设计教程(第三版)课后习题12.3 (C语言代码)浏览:583 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2233 |