首页 > 编程语言 > 详细

51-迷宫(一)- java版dfs和bfs

时间:2019-03-21 23:58:20      阅读:100      评论:0      收藏:0      [点我收藏+]

标签:ret   []   adding   一次   get   dfs   lse   字符串   span   

一天蒜头君掉进了一个迷宫里面,蒜头君想逃出去,可怜的蒜头君连迷宫是否有能逃出去的路都不知道。

看在蒜头君这么可怜的份上,就请聪明的你告诉蒜头君是否有可以逃出去的路。

输入格式

第一行输入两个整数 nn 和 mm,表示这是一个 n \times mn×m 的迷宫。

接下来的输入一个 nn 行 mm 列的迷宫。其中 ‘S‘ 表示蒜头君的位置,‘*‘表示墙,蒜头君无法通过,‘.‘表示路,蒜头君可以通过‘.‘移动,‘T‘表示迷宫的出口(蒜头君每次只能移动到四个与他相邻的位置——上,下,左,右)。

输出格式

输出一个字符串,如果蒜头君可以逃出迷宫输出"yes",否则输出"no"

数据范围

1 \le n, m \le 101n,m10。

输出时每行末尾的多余空格,不影响答案正确性

样例输入1

3 4
S**.
..*.
***T

样例输出1

no

样例输入2

3 4
S**.
....
***T

样例输出2

yes

 

bfs:  就是遍历周围的格子,能走的放入到一个Stack里面,然后放完,就一次去取,一层一层的取,注意要用一个 visit判断是否以前放入了,一旦重复放入那就会死循环。

import java.util.Scanner;
import java.util.Stack;

public class Main{
	public static String mp[] = new String[11];
	public static int visit[][] = new int[11][11];
	public static int ans = 0;
	public static int n, m;
	
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		n = cin.nextInt();
		m = cin.nextInt();
		
		for(int i = 0; i < n; i++) {
			mp[i] = cin.next(); 
//			System.out.println(i + mp[i]);
		}
//		System.out.println("-----");
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(mp[i].charAt(j) == ‘S‘) {
					dfs(i,j);
					break;
				}
			}
		}
		if(ans == 0) {
			System.out.println("no");
		}
		else {
			System.out.println("yes");
		}
	}
	
	public static void dfs(int x0, int y0) {
		node no = new node(x0, y0);
		Stack<node> stack = new Stack<node>();
		stack.add(no);
		visit[x0][y0] = 1;
		int dx[] = {0, 0, 1, -1};
		int dy[] = {1, -1, 0, 0};
		
		while(!stack.empty()) {
			node nd = stack.pop();
			for(int i = 0; i < 4; i++) {
				int x = nd.x + dx[i];
				int y = nd.y + dy[i];
				if(x >= 0 && x < n && y >= 0 && y < m && 
						visit[x][y] == 0 && mp[x].charAt(y) != ‘*‘) {
					if(mp[x].charAt(y) == ‘T‘) {
						ans = 1;
						return ;
					}
					else {
						node temp = new node(x, y);
						stack.add(temp);
						visit[x][y] = 1;
					}
				}
			}
			
		}
		
	}
	 
}

class node{
	int x, y;
	node(){
		
	}
	node(int x0, int y0){
		this.x = x0;
		this.y = y0;
	}
}

 

  

dfs: 

import java.util.Scanner;

public class Main1{
	public static String mp[] = new String[11];
	public static int[][] visit = new int[11][11];
	public static int n, m, ans;
	public static int dx[] = {0, 0, 1, -1};
	public static int dy[] = {1, -1, 0, 0};
	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		n = cin.nextInt();
		m = cin.nextInt();
		
		for(int i = 0; i < n; i++) {
			mp[i] = cin.next();
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(mp[i].charAt(j) == ‘S‘) {
					visit[i][j] = 1;
					dfs(i, j);
					break;
				}
			}
		}
		if(ans == 1) {
			System.out.println("yes");
		}
		else {
			System.out.println("no");
		}
	}
	public static void dfs(int x0, int y0) {
		if(mp[x0].charAt(y0) == ‘T‘) {
			ans = 1;
			return ;
		}
		for(int i = 0; i < 4; i++) {
			int x = x0 + dx[i];
			int y = y0 + dy[i];
			if(x >= 0 && x < n && y >= 0 && y < m
					&& visit[x][y] == 0 && mp[x].charAt(y) != ‘*‘) {
				visit[x][y] = 1;
				dfs(x, y);
				visit[x][y] = 0;
			}
		}
	}
	
}

  

51-迷宫(一)- java版dfs和bfs

标签:ret   []   adding   一次   get   dfs   lse   字符串   span   

原文:https://www.cnblogs.com/zhumengdexiaobai/p/10575615.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号