【搜索】BFS广度优先搜索 - 木东驿站 - Powered by MoodBlog

CONTENT

【搜索】BFS广度优先搜索

题目描述

小明置身于一个迷宫,请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。

输入

输入包含多组测试数据。输入的第一行是一个整数T,表示有T组测试数据。
每组输入的第一行是两个整数N和M(1<=N,M<=100)。
接下来N行,每行输入M个字符,每个字符表示迷宫中的一个小方格。
字符的含义如下:
‘S’:起点
‘E’:终点
‘-’:空地,可以通过
‘#’:障碍,无法通过
输入数据保证有且仅有一个起点和终点。

输出

对于每组输入,输出从起点到终点的最短路程,如果不存在从起点到终点的路,则输出-1。

样例输入

1
5 5
S-###
-----
##---
E#---
---##

样例输出

9

好久没有写过搜索算法了,有些生疏,下面给出BFS求解的JAVA代码

import java.util.Scanner;
public class Test{ 
	/*
	 * 迷宫字符串
	 * 行走记录x
	 * 行走记录y
	 * 步数记录step
	 * 起点x
	 * 起点y
	 * 行数mm
	 * 列数nn
	 */
	public static class Step{
		int x=0;
		int y=0;
		int num=0;
	}
	public static int bfs(char[][] data,Step[] step,int x,int y,int mm,int nn){
			int n = 0,m=0;
			step[n].x = x;
			step[n].y = y;
			data[y][x] = '#';
			step[n].num = 0;
			n = -1;
			while(n<m){
				n++;
				for(int i=0;i<5;i++){
					int xx=step[n].x,yy=step[n].y;
					switch(i){
					case 0:
						xx++;
						break;
					case 1:
						xx--;
						break;
					case 2:
						yy++;
						break;
					case 3:
						yy--;
						break;
					default:
						break;
					}
					
					if(xx>=0&&xx<nn&&yy>=0&&yy<mm){
						if(data[yy][xx]=='-'||data[yy][xx]=='S'){
							m++;
							step[m].x =  xx;
							step[m].y =  yy;
							step[m].num = step[n].num+1;
							data[yy][xx] = '#';
						}else if(data[yy][xx]=='E'){
							return step[n].num+1;
						}
					}
				}			
			}

		return -1;
	}
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int nn = scanner.nextInt();
		while(nn!=0){
			int m=scanner.nextInt(),n=scanner.nextInt();
			char[][] data = new char[m][n];
			
			Step step[] = new Step[9999];
			for(int i=0;i<9999;i++){
				step[i] = new Test.Step();
			}
			int x=0,y=0;
			for(int i=0;i<m;i++){
				String s = scanner.next();
				for(int j=0;j<n;j++){
					data[i][j] = s.charAt(j);
					if(data[i][j]=='S'){
						x = j;
						y = i;
					}
				}
			}
			System.out.println(bfs(data,step,x,y,m,n));	
			nn--;
		}
	}
}


个快快 2017年11月02日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号