内存:128  时间:1

题目描述

Given a maze, find a shortest path from start to goal.

输入

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.

输出

For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.

样例输入

1
5 5
S-###
—–
##—
E#—
—##

样例输出

9

提示

代码如下

import java.util.*;
public class Main {
	static int[][] map=new int[101][101];
	static int[][] vis=new int[101][101];
	static int[][] dis=new int[101][101];
	static int[] qu=new int[10001];
	static int[] dx= {-1,0,1,0};
	static int[] dy= {0,1,0,-1};
	static int x1,y1,x2,y2;
	static int m,n;
	public static int bfs(int x,int y) {
		int u,nx,ny;
		int front=0,rear=0;
		u=x*m+y;
		vis[x][y]=1;
		dis[x][y]=0;
		qu[rear++]=u;
		while(front<rear) {
			u=qu[front++];
			x=u/m;
			y=u%m;
			for(int i=0;i<4;i++) {
				nx=x+dx[i];ny=y+dy[i];
				if(nx>=0&&nx<m&&ny>=0&&ny<n&&vis[nx][ny]==0&&map[nx][ny]==1) {
					int v=0;
					v=nx*m+ny;
					qu[rear++]=v;
					vis[nx][ny]=1;
					dis[nx][ny]=dis[x][y]+1;
					if(nx==x2&&ny==y2)
						return dis[nx][ny];
				}
			}
		}
		return -1;
	}
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int t=in.nextInt();
		while(t>0) {
			String s="";
			char[][] c=new char[101][101];
			m=in.nextInt();n=in.nextInt();
			s=in.nextLine();
			for(int i=0;i<m;i++)
				for(int j=0;j<n;j++) {
					map[i][j]=0;
					vis[i][j]=0;
					dis[i][j]=0;
				}
			for(int i=0;i<m;i++) {
				s=in.nextLine();
				for(int j=0;j<n;j++) {
					c[i][j]=s.charAt(j);
					switch(c[i][j]) {
						case 'S':map[i][j]=1;x1=i;y1=j;break;
						case 'E':map[i][j]=1;x2=i;y2=j;break;
						case '-':map[i][j]=1;break;
						case '#':map[i][j]=0;break;
					}
				}
			}
			System.out.println(bfs(x1,y1));
			t--;
		}
	}
}

代码来源于互联网,仅供参考!