（Java实现）营救

问题 B: 营救

时间限制: 1 Sec 内存限制: 128 MB

题目描述

    铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。

    通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。

   为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。

输入

第一行为n,下面是一个n*n的0、1矩阵，表示海洋地图

最后一行为四个小于n的整数，分别表示哥伦比亚号和铁塔尼号的位置。

输出

哥伦比亚号到铁塔尼号的最短距离.

样例输入

3

0 0 1

1 0 1

1 0 0

1 1 3 3

样例输出

4

提示

N<=1000

题解

输入那里我卡了很久，请注意输入的处理

import java.util.Scanner;

public class yingjiu {

	public static int x1, y1, x2, y2, n, step = 0, min = Integer.MAX_VALUE;

	public static boolean[][] bool;

	public static int[][] num;

	public static int[] a = { 0, 1, 0, -1 };

	public static int[] b = { -1, 0, 1, 0 };

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();

		num = new int[n + 1][n + 1];

		bool = new boolean[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= n; j++) {

				num[i][j] = sc.nextInt();

			}

		}

		x1 = sc.nextInt();

		y1 = sc.nextInt();

		x2 = sc.nextInt();

		y2 = sc.nextInt();

		dfs(x1, y1);

		System.out.println(min);

	}

	public static void dfs(int x, int y) {

		if (x == x2 && y == y2) {

			min = Math.min(min, step);

			return;

		}

		for (int i = 0; i < 4; i++) {

			if (x + a[i] <= n && x + a[i] > 0 && y + b[i] <= n && y + b[i] > 0) {

				if (num[x + a[i]][y + b[i]] == 0) {

					if (!bool[x + a[i]][y + b[i]]) {

						bool[x + a[i]][y + b[i]] = true;

						step++;

						dfs(x + a[i], y + b[i]);

						step--;

						bool[x + a[i]][y + b[i]] = false;

					}

				}

			}

		}

	}

}

巴特西

（Java实现）营救

题解

输入那里我卡了很久，请注意输入的处理

最新文章

热门文章

巴特西

（Java实现） 营救

题解 输入那里我卡了很久，请注意输入的处理

最新文章

热门文章

（Java实现）营救

题解

输入那里我卡了很久，请注意输入的处理