1101. 献给阿尔吉侬的花束

本文主要是介绍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 stubfor (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;}}

这篇关于1101. 献给阿尔吉侬的花束的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---