仙岛求药 —— dfs 与 bfs求解

样例输入1

8 8
.@##…#
#…#.#
#.#.##…
…#.###.
#.#…#.
…###.#.
…#.*…
.#…###

样例输出1

10

样例输入2

9 6
.#…#.
.#.*.#
.####.
…#…
…#…
…#…
…#…
#.@.##
.#…#.

样例输出2

-1

dfs

ps:使用dfs会运行超时，30组测试数据只能通过部分，其实这种最短路径、最少操作的问题最好还是靠bfs解决。

import java.util.Scanner;
//最短路径
public class Main{
	static int min=9999;  //步数
	static int []dx = {-1,0,0,1};
	static int []dy = {0,-1,1,0};
	static boolean flag = false;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt(); //n行
    	int m = sc.nextInt(); //m列
    	sc.nextLine();
    	char [][]table = new char[n][];
    	int [][]vis = new int[n][m];  //标记是否已访问    
    	for(int i=0;i<n;i++)
    		table[i] = sc.nextLine().toCharArray();
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++)
    		    if(table[i][j] == '@'){
    		    	dfs(table,n,m,i,j,vis,0);	
    		    }
    	    }
    	    
    	if(flag == true) System.out.println(min);
    	else System.out.println(-1);
   }

	private static void dfs(char[][] table, int n, int m, int i, int j,int[][] vis,int step) {
		if(table[i][j] == '*')  {  
			if(step < min) 
				min = step;
			return;
		}
		 
		for(int u=0;u<4;u++){
			int x = i+dx[u],y=j+dy[u];
			if(x>=0 && x<n && y>=0 && y<m && table[x][y] != '#' && vis[x][y] == 0){
				vis[x][y] = 1;  //已访问
				dfs(table, n, m, x, y, vis,step+1);
				vis[x][y] = 0; //回溯	
			}	
		}
		return;
	}  
}

bfs

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static int step = -1;  //步数
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt(); 
    	int m = sc.nextInt(); 
    	sc.nextLine();
    	char [][]graph = new char[n][];
    	int [][]vis = new int[n][m];
    	
    	Queue<Node> queue = new LinkedList<>();
    	for(int i=0;i<n;i++)
    		graph[i] = sc.nextLine().toCharArray();
    	
    	for(int i =0;i<n;i++){
    		for(int j=0;j<m;j++){
    			if(graph[i][j] == '@')  queue.add(new Node(i,j,0));
    		}
    	}
    	
    	while(!queue.isEmpty()){
    		Node poll = queue.poll();
    		int x = poll.i;
    		int y = poll.j;
    		int deep = poll.depth;
    		vis[x][y] = 1;  //标记已访问
    		
    		//到达出口
    		if(graph[x][y] == '*'){
    			step = poll.depth;
    			break;
    		}
    		  		
    		//添加四个邻居
    		if(x-1 >=0 && x-1 < n  && graph[x-1][y] != '#' && vis[x-1][y] == 0){
    			queue.add(new Node(x-1,y,deep+1));
    		}
    		if(x+1 >=0 && x+1 < n  && graph[x+1][y] != '#' && vis[x+1][y] == 0){
    			queue.add(new Node(x+1,y,deep+1));
    		}
    		if(y-1 >=0 && y-1 < m  && graph[x][y-1] != '#' && vis[x][y-1] == 0){
    			queue.add(new Node(x,y-1,deep+1));
    		}
    		if(y+1 >=0 && y+1 < m  && graph[x][y+1] != '#' && vis[x][y+1] == 0){
    			queue.add(new Node(x,y+1,deep+1));
    		}
    	}
    	 System.out.print(step);
    }

	  static class Node{
		int i;
		int j;
		int depth;  //深度
		
		public Node(int i,int j,int depth){
			this.i = i;
			this.j = j;
			this.depth = depth;
		}
	  }
}