社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
题目如下 ：
本题采用广度优先搜索解决，广度优先搜索相对于深度优先搜索我觉得较为容易理解，因为不用递归和回溯，用循环就可以解决，广度优先搜索的有点在于扫描搜索树的顺序是从根节点往下一层一层的搜索，搜索在求解最优解的时候比深度有优势，因为深度要求最优解的话需要遍历所有结果才能得出，但是广度优先搜索扫描到的第一个结果就是最优结果，具体的代码如下：
import java.util.*;class Point{int x,y,step;public Point(int x,int y,int step){this.x=x;this.y=y;this.step=step;}}public class BFSMigong1 { static char[][] datas = null; static int[][] visit = null; static int[][] oprate = {{0,1},{1,0},{0,-1},{-1,0}}; static int result = -1;public static void main(String[] args) {// TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); datas = new char[n+2][m+2]; visit = new int[n+2][m+2]; int startX=0,startY=0; String temp = null; for(int i=1;i<=n;i++){ temp = sc.next(); for(int j=1;j<=m;j++){ datas[i][j] = temp.charAt(j-1); if(datas[i][j] == 'S'){ startX=i; startY=j; } } } bfs(startX,startY); System.out.print(result);}public static void bfs(int x,int y){Queue<Point> queue = new LinkedList<Point>();Point p = new Point(x,y,0); //插入根节点queue.offer(p);Point temp = null;
visit[x][y]=1; boolean isFind = false;
while(!queue.isEmpty()){
temp = queue.poll(); //从开头弹出一个节点
for(int i=0;i<4;i++){ //遍历这个节点对应的位置能够到达的位置
if(visit[temp.x+oprate[i][0]][temp.y+oprate[i][1]]==0&&datas[temp.x+oprate[i][0]][temp.y+oprate[i][1]]!='#'&&datas[temp.x+oprate[i][0]][temp.y+oprate[i][1]]!=' '){
visit[temp.x+oprate[i][0]][temp.y+oprate[i][1]]=1;
if(datas[temp.x+oprate[i][0]][temp.y+oprate[i][1]]=='T'){//因为在这个题目中初始位置不可能是目标位置，所以在这里判断能够少走一层
result = temp.step+1; //在下一层到达，所以结果要这一个位置的步数+1
isFind = true;
break;
}else{
queue.offer(new Point(temp.x+oprate[i][0],temp.y+oprate[i][1],temp.step+1));
}
}
}
if(isFind){
break ;
}
}
}
}
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
