1101. 献给阿尔吉侬的花束

Problem: 1101. 献给阿尔吉侬的花束

思路

这道题目让我们求出开始点S到结束点E的最短路径，题目中说，字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。我们可以将起点和终点看作是两个不同的状态，然后使用BFS来搜索最短的路径。在搜索的过程中，我们需要记录到达每个状态的最小代价

解题方法

定义一个二维数组matrix来表示迷宫的布局：S表示起点，E表示终点，#表示墙壁，.表示可以通行的空地。
从输入中读取迷宫的行数x和列数y。
使用一个循环读取迷宫的每一行，并将其存储在matrix中。
使用两个变量startx和starty来记录起点的坐标，使用两个变量endx和endy来记录终点的坐标。遍历迷宫，当找到S时，将其坐标赋值给startx和starty；当找到E时，将其坐标赋值给endx和endy。
创建一个二维数组vis来记录到达每个状态的最小代价。初始化vis的所有元素为-1，表示尚未访问过。
创建一个队列queue来进行BFS搜索。将起点的坐标(startx, starty)添加到队列中，并将其代价vis[startx][starty]设置为0。
进入循环，直到队列为空为止。每次从队列中取出一个状态，记为当前位置(nx, ny)。
遍历当前位置的上、下、左、右四个相邻位置，记为(dx, dy)。
对于每个相邻位置(dx, dy)，进行如下判断：
如果(dx, dy)超出了迷宫的边界，或者已经访问过(vis[dx][dy]!=-1)，或者是墙壁(matrix[dx][dy]==‘#’)，则忽略该相邻位置，继续循环。
否则，将相邻位置(dx, dy)的代价值vis[dx][dy]更新为当前位置(nx, ny)的代价值vis[nx][ny]+1，并将相邻位置(dx, dy)添加到队列中。
如果相邻位置(dx, dy)恰好是终点的位置(endx, endy)，则返回其代价值vis[dx][dy]，即为最短路径的长度。
如果循环结束后仍未找到终点，说明不存在从起点到终点的路径，返回-1

复杂度

时间复杂度:

$O(x\ast y)$，其中x和y分别为迷宫的行数和列数。由于需要遍历整个迷宫，时间复杂度为$O(x\ast y)$。

空间复杂度:

$O(x\ast y)$，其中$x$和$y$分别为迷宫的行数和列数。需要使用数组$vis$来记录到达每个状态的最小代价，所以空间复杂度为$O(x\ast y)$。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	static StreamTokenizer sr = new StreamTokenizer(in);
	static int t, x, y, step = 0;
	static int MAXR = 210;
	static char[][] matrix = new char[MAXR][MAXR];
	static int l, r;
//	static int[][] queue = new int[MAXR][2];
	static int[][] vis = new int[MAXR][MAXR];
	static int[][] move = { {}, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
	static Queue<int[]> queue = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		t = nextInt();
		for (int a = 0; a < t; a++) {
			x = nextInt();
			y = nextInt();
// 			in.readLine();
			for (int i = 0; i < x; i++) {
				matrix[i] = in.readLine().toCharArray();
			}
			int startx = 0, starty = 0, endx = 0, endy = 0;
			for (int i = 0; i < x; i++) {
				for (int j = 0; j < y; j++) {
					if (matrix[i][j] == 'S') {
						startx = i;
						starty = j;
					} else if (matrix[i][j] == 'E') {
						endx = i;
						endy = j;
					}
				}
			}
			int res = bfs(startx, starty, endx, endy);
			out.println(res == -1 ? "ops!" : res);
		}
		out.flush();
	}

	private static int bfs(int startx, int starty, int endx, int endy) {
		// TODO Auto-generated method stub
		for (int i = 0; i < x; i++) {
			Arrays.fill(vis[i], -1);
		}
		queue.clear();
		queue.offer(new int[] { startx, starty });
		vis[startx][starty] = 0;
		while (!queue.isEmpty()) {
			int[] arr = queue.poll();
			int nx = arr[0];
			int ny = arr[1];
			// 开枝散叶
			for (int i = 1; i <= 4; i++) {
				int dx = nx + move[i][0];
				int dy = ny + move[i][1];
				// 边界判断
				if (dx >= x || dy >= y || dx < 0 || dy < 0 || vis[dx][dy] != -1 || matrix[dx][dy] == '#')
					continue;
				vis[dx][dy] = vis[nx][ny] + 1;
				if (dx == endx && dy == endy) {
					return vis[dx][dy];
				}
				queue.offer(new int[] { dx, dy });
			}
		}
		return -1;
	}

	static int nextInt() throws IOException {
		sr.nextToken();
		return (int) sr.nval;
	}

}