欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深搜-迷宫

程序员文章站 2022-03-03 11:13:11
...
 package aha;

import java.util.Scanner;

public class migong_dfs {
	static int n;
	static int m;
	static int book[][] = new int[51][51];
	static int a[][] = new int[51][51];
	static int p;
	static int q;
	static int min = 999;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		p = sc.nextInt();
		q = sc.nextInt();
		book[1][1] = 1;
		dfs(1, 1, 0);
		System.out.println(min);
	}

	private static void dfs(int x, int y, int s) {
		int tx = 0, ty = 0;
		if (p == x && q == y) {
			if (min > s) {
				min = s;
			}
			return;
		}
		int next[][] = {{0,1},{1,0},{0,-1},{-1,0}};//{ { 1, 0 }, { 0,1 }, {-1,0 }, { 0,-1 } };
		for (int i = 0; i <= 3; i++) {
			tx = x + next[i][0];
			ty = y + next[i][1];

			if (tx < 1 || tx >n|| ty < 1 || ty > m) {
				continue;
			}
			if(book[tx][ty]==0&&a[tx][ty]==0){
				book[tx][ty]=1;
				
				dfs(tx,ty,s+1);
				book[tx][ty]=0;
			}
		}
		return ;
	}
}/*
5 4
0 0 1 0
0 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1
3 4*/