題目描述：
阿爾吉儂是一只聰明又慵懶的小白鼠，它最擅長的就是走各種各樣的迷宮，
今天它要挑戰一個非常大的迷宮，研究員們為了鼓勵阿爾吉儂盡快到達終點，就在終點放了一塊阿爾吉儂最喜歡的奶酪，
現在研究員們想知道，如果阿爾吉儂足夠聰明，它最少需要多少時間就能吃到奶酪， 迷宮用一個 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!
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int row;
static int col;
static char[][] arr;
static int[][] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = sc.nextInt();
while(count-- > 0) {
row = sc.nextInt();
col = sc.nextInt();
arr = new char[row][col];
visited = new int[row][col];
for(int i = 0; i < row; i++) {
String str = sc.next();
arr[i] = str.toCharArray();
}
int[] st = new int[2];
int[] ed = new int[2];
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(arr[i][j] == 'S') {
st = new int[]{i, j};
}
}
}
System.out.println(bfs(st));
}
}
public static String bfs(int[] st) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{st[0], st[1]});
arr[st[0]][st[1]] = '#';
while(!queue.isEmpty()) {
int[] cur = queue.poll();
int x = cur[0];
int y = cur[1];
for(int d = 0; d < 4; d++) {
int x1 = x + dx[d];
int y1 = y + dy[d];
if(x1 < 0 || y1 < 0 || x1 >= row || y1 >= col ||arr[x1][y1] == '#' ) {
continue;
}
if(arr[x1][y1] == 'E') {
return visited[x][y] + 1 + "";
}
visited[x1][y1] = visited[x][y] + 1;
arr[x1][y1] = '#';
queue.add(new int[]{x1, y1});
}
}
return "oop!";
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259678.html
標籤：其他