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