Maze Problem
Time Limit: 1 Sec Memory Limit: 128 MB
Given a maze, find a shortest path from start to goal.

传送门:SHUOJ1021
Input
Input consists serveral test cases.

First line of the input contains number of test case T.

For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ).

Each of the following N lines contain M characters. Each character means a cell of the map.

Here is the definition for chracter.

Constraint:

For a character in the map:
‘S’ : start cell
‘E’ : goal cell
‘-‘ : empty cell
‘#’ : obstacle cell
no two start cell exists.
no two goal cell exists.
Output
For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.

题解

简单bfs
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.*;  
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
public class Main {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
for(int o=1;o<=t;o++){
int m=sc.nextInt();
int n=sc.nextInt();
int[][]maze=new int[m][n];
int rows=0,cols=0;
for(int i=0;i<m;i++){
String s=sc.next();
for(int j=0;j<n;j++){
maze[i][j]=s.charAt(j);
if(maze[i][j]=='S'){
rows=i;
cols=j;
}
}
}
pw.println(bfs(rows,cols,maze,m,n));
pw.flush();
}
}
static int bfs(int i,int j,int[][]maze,int m,int n){
LinkedBlockingQueue<Node>queue=new LinkedBlockingQueue<Node>();
queue.add(new Node(i,j,0));
boolean[][] jl=new boolean[m][n];
jl[i][j]=true;
while(!queue.isEmpty()){
Node temp=queue.poll();
if(maze[temp.i][temp.j]=='E') return temp.count;

if(judge(temp.i-1,temp.j,m,n,maze)){
if(!jl[temp.i-1][temp.j]){
jl[temp.i-1][temp.j]=true;
queue.add(new Node(temp.i-1,temp.j,temp.count+1));
}
}
if(judge(temp.i,temp.j-1,m,n,maze)){
if(!jl[temp.i][temp.j-1]){
jl[temp.i][temp.j-1]=true;
queue.add(new Node(temp.i,temp.j-1,temp.count+1));
}
}
if(judge(temp.i,temp.j+1,m,n,maze)){
if(!jl[temp.i][temp.j+1]){
jl[temp.i][temp.j+1]=true;
queue.add(new Node(temp.i,temp.j+1,temp.count+1));
}
}
if(judge(temp.i+1,temp.j,m,n,maze)){
if(!jl[temp.i+1][temp.j]){
jl[temp.i+1][temp.j]=true;
queue.add(new Node(temp.i+1,temp.j,temp.count+1));
}
}
}
return 0;
}
static boolean judge(int i,int j,int m,int n,int[][]maze){
if(i<0||i>=m||j<0||j>=n||maze[i][j]=='#')return false;
return true;
}
}
class Node{
int i;
int j;
int count;
Node(int a,int b,int c){
i=a;
j=b;
count=c;
}
}