獻給阿爾吉儂的花束
題目來源：《資訊學奧賽一本通》
時間限制：\(1000ms\) 記憶體限制：\(64mb\)
題目描述
阿爾吉儂是一只聰明又慵懶的小白鼠，它最擅長的就是走各種各樣的迷宮，
今天它要挑戰一個非常大的迷宮，研究員們為了鼓勵阿爾吉儂盡快到達終點，就在終點放了一塊阿爾吉儂最喜歡的奶酪，
現在研究員們想知道，如果阿爾吉儂足夠聰明，它最少需要多少時間就能吃到奶酪，
迷宮用一個 \(R*C\) 的字符矩陣來表示，
字符 \(S\) 表示阿爾吉儂所在的位置，字符 \(E\) 表示奶酪所在的位置，字符 \(\#\) 表示墻壁，字符 \(.\) 表示可以通行，
阿爾吉儂在 \(1\) 個單位時間內可以從當前的位置走到它上下左右四個方向上的任意一個位置，但不能走出地圖邊界，
輸入格式
第一行是一個正整數 \(T\) ，表示一共有 \(T\) 組資料，
每一組資料的第一行包含了兩個用空格分開的正整數 \(R\) 和 \(C\) ，表示地圖是一個 \(R*C\) 的矩陣，
接下來的 \(R\) 行描述了地圖的具體內容，每一行包含了 \(C\) 個字符，字符含義如題目描述中所述，保證有且僅有一個 \(S\) 和 \(E\) ，
輸出格式
對于每一組資料，輸出阿爾吉儂吃到奶酪的最少單位時間，
若阿爾吉儂無法吃到奶酪，則輸出“oop!”（只輸出引號里面的內容，不輸出引號），
每組資料的輸出結果占一行，
資料范圍
\(1 < T ≤ 10\) ,
\(2 ≤ R,C ≤ 200\)
樣例輸入
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.
樣例輸出
5
1
oop!
解題思路：BFS
拿到給定的 \(R*C\) 的陣列后，先遍歷拿到 \(S\) 和 \(E\) 的坐標，用pair類物件來保存，
BFS思路： 將當前坐標的上下左右四個格子遍歷一邊，如果能走，就將能走的格子的坐標放入佇列，回圈內依次出列，再繼續遍歷出列的格子的上下左右，如此回圈，知道沒有格子可以走，即佇列為空，就結束，
先將起始坐標入隊，開一個 \(dist\) 陣列用于保存距離，并將起始坐標的距離寫為0，
進入回圈，出隊一個 pair t ，遍歷此坐標的上下左右四個格子，如果能走，則將其坐標入隊，并直接賦值距離 dist[x][y] = dist[t.x][t.y] + 1 ，所有走過的格子將其標記為不能走，
回圈直到走到了終點坐標即回傳終點坐標距離 dist[e.x][e.y] ，如果佇列為空的時候還未走到終點，回圈結束，回傳 oop!，
類似題目： 2021寒假每日一題《紅與黑》
解題代碼-Java
import java.util.Queue;
import java.util.Scanner;
import java.util.LinkedList;
class pair {
int x, y;
public pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int r, c;
static char[][] maze;
static int[][] dist;
static int[] dx = new int[]{0, 1, 0, -1};
static int[] dy = new int[]{-1, 0, 1, 0};
static String bfs(pair s, pair e) {
Queue<pair> q = new LinkedList<>();
q.offer(s);
dist[s.x][s.y] = 0;
while (!q.isEmpty()) {
pair t = q.poll();
for (int i = 0; i < 4; i++) {
int x = t.x + dx[i], y = t.y + dy[i];
if (x >= 0 && x < r && y >= 0 && y < c && maze[x][y] != '#') {
maze[x][y] = '#';
dist[x][y] = dist[t.x][t.y] + 1;
if (x == e.x && y == e.y) {
return "" + dist[x][y];
}
q.offer(new pair(x, y));
}
}
}
return "oop!";
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int t = input.nextInt();
while (t-- > 0) {
r = input.nextInt();
c = input.nextInt();
maze = new char[r][c];
dist = new int[r][c];
pair s = null, e = null;
for (int i = 0; i < r; i++) {
maze[i] = input.next().toCharArray();
for (int j = 0; j < c; j++) {
if (maze[i][j] == 'S') {
s = new pair(i, j);
}
if (maze[i][j] == 'E') {
e = new pair(i, j);
}
}
}
System.out.println(bfs(s, e));
}
input.close();
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256225.html
標籤：其他
上一篇：MATLAB中FFT_HDL_Optimized模塊定點（IEEE754單精度float格式）二進制與十進制轉換實作
下一篇：FFT HDL Optimized模塊HDL綜合代碼生成及與Xilinx xfft IP MEX介面精度詳細比較