USACO - 2.4.2 - Overfencing

 

原创文章转载请注明出处

摘要：动态规划

一. 题目翻译

1. 描述：

农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽度W(1<=W<=38)及高度H(1<=H<=100)。 2*H+1行，每行2*W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点，走出迷宫的最少步数）。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X或Y轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）这是一个W=5,H=3的迷宫：

如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。

2. 格式：

          INPUT FORMAT:

          (file maze1.in)

          第一行： W和H（用空格隔开） 

  第二行至第2 * H + 1行：  每行2 * W + 1个字符表示迷宫

          OUTPUT FORMAT:

          (file maze1.out)

          输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。

3. SAMPLE：

          SAMPLE INPUT:

 5 3

+-+-+-+-+-+

|         |

+-+ +-+ + +

|     | | |

+ +-+-+ + +

| |     |  

+-+ +-+-+-+

          SAMPLE OUTPUT:

9

          

二.  题解

1. 题意理解（将问题分析清楚，大致用什么思路）：

          我们首先从输入输出中查找出迷宫的两个入口，然后以这两个入口为起点做floodfill为每个点产生同入口之间距离。然后遍历整个迷宫找出距离最远的输出即可。

 

2. 具体实现（具体实现过程中出现的问题）：

          floodfill图论当中的基本问题，注意积累一下。

三.  代码

/*
ID:fightin1
LANG:JAVA
TASK:maze1
*/
package session_2_4_2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class maze1 {

	public static void main(String[] args) throws Exception {
		Scanner in = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
//		Scanner in = new Scanner(new BufferedReader(new FileReader(
//		"maze1.in")));
//		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
//		"maze1.out")));
		
		int width = in.nextInt();
		int height = in.nextInt();
		in.nextLine();

		char[][] maze = new char[2 * height + 1][2 * width + 1];
		int[][] cnt = new int[2 * height + 1][2 * width + 1];
		int x1 = 0, y1 = 0;
		int x2 = 0, y2 = 0;

		for (int i = 0; i < 2 * height + 1; i++) {
			String line = in.nextLine();
			for (int j = 0; j < 2 * width + 1; j++) {
				char temp = line.charAt(j);
				maze[i][j] = temp;
				cnt[i][j] = Integer.MAX_VALUE;
				if (temp == ' ') {
					int tempx = 0;
					int tempy = 0;
					if (i == 0) {
						tempx = i + 1;
						tempy = j;
					}
					if (i == 2 * height) {
						tempx = i - 1;
						tempy = j;
					}
					if (j == 0) {
						tempx = i;
						tempy = j + 1;
					}
					if (j == 2 * width) {
						tempx = i;
						tempy = j - 1;
					}
					if (tempx!=0||tempy!=0){
						if (x1 == 0 && y1 == 0) {
							x1 = tempx;
							y1 = tempy;
						} else {
							x2 = tempx;
							y2 = tempy;
						}
					}
				}
			}
		}
		cnt[x1][y1] = 1;
		flood(x1, y1, cnt, maze, width, height);
		cnt[x2][y2] = 1;
		flood(x2, y2, cnt, maze, width, height);
		int max = 0;
		for (int i = 1; i < 2 * height + 1; i += 2) {
			for (int j = 1; j < 2 * width + 1; j += 2) {
				int temp = cnt[i][j];
				if (cnt[i][j] != Integer.MAX_VALUE) {
					if (max < cnt[i][j]) {
						max = cnt[i][j];
					}
				}
			}
		}
		pw.println(max);
		pw.close();
	}

	public static void flood(int x, int y, int[][] cnt, char[][] maze,
			int width, int height) {
		if (cnt[x][y] != 0) {
			if (x + 2 < 2 * height + 1 && maze[x + 1][y] == ' ') {
				if (cnt[x + 2][y] > cnt[x][y] + 1) {
					cnt[x + 2][y] = cnt[x][y] + 1;
					flood(x + 2, y, cnt, maze, width, height);
				}

			}
			if (x - 2 >= 0 && maze[x - 1][y] == ' ') {
				if (cnt[x - 2][y] > cnt[x][y] + 1) {
					cnt[x - 2][y] = cnt[x][y] + 1;
					flood(x - 2, y, cnt, maze, width, height);
				}

			}
			if (y + 2 < 2 * width + 1 && maze[x][y+1] == ' ') {
				if (cnt[x][y + 2] > cnt[x][y] + 1) {
					cnt[x][y + 2] = cnt[x][y] + 1;
					flood(x, y + 2, cnt, maze, width, height);
				}

			}
			if (y - 2 >= 0 && maze[x][y-1] == ' ') {
				if (cnt[x][y - 2] > cnt[x][y] + 1) {
					cnt[x][y - 2] = cnt[x][y] + 1;
					flood(x, y - 2, cnt, maze, width, height);
				}
			}
		}
	}
}