首页 > 试题广场 >

Hero

[编程题]Hero
  • 热度指数:1437 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
500年前,nowcoder是我国最卓越的剑客。他英俊潇洒,而且机智过人^_^。 突然有一天,nowcoder 心爱的公主被魔王困在了一个巨大的迷宫中。nowcoder 听说这个消息已经是两天以后了,他知道公主在迷宫中还能坚持T天,他急忙赶到迷宫,开始到处寻找公主的下落。 时间一点一点的过去,nowcoder 还是无法找到公主。最后当他找到公主的时候,美丽的公主已经死了。从此nowcoder 郁郁寡欢,茶饭不思,一年后追随公主而去了。T_T 500年后的今天,nowcoder 托梦给你,希望你帮他判断一下当年他是否有机会在给定的时间内找到公主。 他会为你提供迷宫的地图以及所剩的时间T。请你判断他是否能救出心爱的公主。

输入描述:
题目包括多组测试数据。
每组测试数据以三个整数N,M,T(00)开头,分别代表迷宫的长和高,以及公主能坚持的天数。
紧接着有M行,N列字符,由".","*","P","S"组成。其中
"." 代表能够行走的空地。
"*" 代表墙壁,redraiment不能从此通过。
"P" 是公主所在的位置。
"S" 是redraiment的起始位置。
每个时间段里redraiment只能选择“上、下、左、右”任意一方向走一步。
输入以0 0 0结束。


输出描述:
如果能在规定时间内救出公主输出“YES”,否则输出“NO”。
示例1

输入

4 4 10
....
....
....
S**P
0 0 0

输出

YES
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNextLine()) {
			String s = sc.nextLine();
			if(s.equals("0 0 0")) break;
			String[] split = s.trim().split("\\s+");
			int n = Integer.parseInt(split[0]);
			int m = Integer.parseInt(split[1]);
			int t = Integer.parseInt(split[2]);
			Character[][] arr = new Character[m][n];
			Node start = new Node();
			Node end = new Node();
			for (int i = 0; i < m; i ++ ) {
				String s1 = sc.nextLine();
				for (int j = 0; j < n; j ++ ) {
					arr[i][j] = s1.charAt(j);
					if(arr[i][j] == 'S') {
						start.x = i;
						start.y = j;
					}
					if(arr[i][j] == 'P') {
						end.x = i;
						end.y = j;
					}
				}
			}
			int[][] direction = {{0, 1}, {0, - 1}, {1, 0}, { - 1, 0}};
			bfs(arr, n, m, t, start, end, direction);
		}
	}
	public static void bfs(Character[][] arr, int n, int m, int t, Node start, Node end, int[][] direction) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(start);
		boolean[][] visited = new boolean[m][n];
		visited[start.x][start.y] = true;
		boolean isFinded = false;
		while ( ! queue.isEmpty()) {
			Node cur = queue.poll();
			if(cur.x == end.x && cur.y == end.y && cur.time <= t) {
				isFinded = true;
				break;
			}
			for (int i = 0; i < 4; i ++ ) {
				Node next = new Node();
				next.x = cur.x + direction[i][0];
				next.y = cur.y + direction[i][1];
				next.time = cur.time + 1;
				if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n && ! visited[next.x][next.y] && arr[next.x][next.y] != '*') {
					queue.add(next);
					visited[next.x][next.y] = true;
				}
			}
		}
		if(isFinded) System.out.println("YES");
		else System.out.println("NO");
	}
	static class Node {
		int x;
		int y;
		int time;
	}
}

发表于 2016-10-07 16:03:28 回复(0)