Newguy


私信TA

用户名:772007765

访问量:88360

签 名:

已秃人士

等  级
排  名 29
经  验 15296
参赛次数 3
文章发表 92
年  龄 0
在职情况 在职
学  校
专  业

  自我简介:

描述

一天,小明梦见自己被外星人抓走了,他被关在了一座监狱里,这座监狱形如N*M(N,M<=200)的矩阵,监狱里有墙、道路和守卫。
小明的小伙伴们得知他被外星人抓走后想要把他救出来,他们要试图接近关押小明的那间房间。当他们经过有守卫的房间时他们必须干掉守卫后继续前进,而当遇到墙的时候则只能绕道。他们只能向上下左右四个方向移动,每移动一次耗时1分钟,干掉一个守卫也耗时1分钟。不必担心,他们足够强壮,可以干掉任何一个守卫。
现在请你计算出他们当中最快到达小明所在房间的那个人最短需要花费多长时间。

输入

输入包含多组测试数据。 每组输入的第一行是两个整数N和M(N,M<=200)。 
接下来N行,每行输入M个字符。“.”代表道路,可以通行。“#”代表墙。“g”代表守卫。“m”代表小明所在的房间。“f”代表每一个小明的小伙伴,可能有多个小伙伴一起来救他。

输出

对于每组输入,输出小伙伴当中最快到达小明所在房间的那个人最短需要花费多长时间。如果所有小伙伴都无法到达小明所在的房间的话,请输出“Poor Xiaoming”(引号不输出)。

样例输入1

7 8
#.#####.
#.m#..f.
#..#g...
..#..#.#
#...##..
.#......

........

样例输出1

13


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

public class Main {
	//节点类
	public static class Node {  
		int l, r;
		int val;
		
		//构造方法
		public Node(int l, int r, int val) {  
			this.l = l;
			this.r = r;
			this.val = val;
		}
		public Node() {
			super();
		}
	}
	
	final static int MAX = 201;
	
	public static int N, M, min;	//N, M, min最小时间
	public static String[] map = new String[MAX];      //监狱
	public static int[][] vis = new int[MAX][MAX];        //标记
	final static int[][] dir = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; //右,左, 上, 下 
	
	//检查节点是否符合条件
	public static boolean CheckNode(Node n) {
		if (n.l >= 0 && n.l < N && n.r >= 0 && n.r < M && map[n.l].charAt(n.r) != '#' && vis[n.l][n.r] == 0)
			return true;
		else
			return false;
	}
	
	//bfs广搜,从小明所在位置反过来搜伙伴
	public static void BFS(Node st) {
		Queue<Node> q = new LinkedList<Node>();   //创造队列
		Node cur;
		st.val = 0;
		q.offer(st);      //添加队头元素
		vis[st.l][st.r] = 1;     //标记
		int count = 0;
		while (!q.isEmpty()) {         //队列非空执行
			cur = q.peek();            //拿出队头元素(非删除)
			if (map[cur.l].charAt(cur.r) == 'f') {
				if (min > cur.val)
					min = cur.val;
				vis[cur.l][cur.r] = 1;
			}
			for (int i = 0; i < 4; i++) {
				Node next = new Node();
				next.l = cur.l + dir[i][0];
				next.r = cur.r + dir[i][1];
				if (CheckNode(next)) {
					if(map[next.l].charAt(next.r) == 'g')      //小明打守卫
						next.val = cur.val + 2;
					else
						next.val = cur.val + 1;
					q.offer(next);           //进队
					if (map[next.l].charAt(next.r) != 'f')
						vis[next.l][next.r] = 1;
				}
			}
			q.poll();
		}
	}
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		while (input.hasNext()) {
			N = input.nextInt();
			M = input.nextInt();
			
			int Ml = 0, Mr = 0;  //小明所在行列
			min = 1 << 20;
			for (int i = 0; i < N; i++) {
				map[i] = new String(input.next());
				for (int j = 0; j < M; j++) {
					vis[i][j] = 0;
					if (map[i].charAt(j) == 'm') {
						Ml = i;
						Mr = j;
					}					
				}
			}
			Node start = new Node(Ml, Mr, 0);
			BFS(start);	
			if (min == 1 << 20)
				System.out.println("Poor Xiaoming");
			else
				System.out.println(min);
		}
	}
}

哪位大佬做出来了教教我,不知道为什么过不了




 

0.0分

8 人评分

  评论区

  • «
  • »