Massive Algorithms: Overfencing

Overfencing - USACO 2.4.2

Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two "exits" for the maze. Even more happily, the maze he created by this overfencing experience is a `perfect' maze: you can find a way out of the maze from any point inside it.

Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the `worst' point in the maze (the point that is `farther' from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move "out" of the maze.

Here's what one particular W=5, H=3 maze looks like:

+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+

Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting.

PROGRAM NAME: maze1

INPUT FORMAT

Line 1:	W and H, space separated
Lines 2 through 2*H+2:	2*W+1 characters that represent the maze

SAMPLE INPUT (file maze1.in)

5 3
+-+-+-+-+-+
|         |
+-+ +-+ + +
|     | | |
+ +-+-+ + +
| |     |  
+-+ +-+-+-+

OUTPUT FORMAT

A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze.

SAMPLE OUTPUT (file maze1.out)

The lower left-hand corner is *nine* steps from the closest exit.

X. Flood fill
http://qingtangpaomian.iteye.com/blog/1635853
我们首先从输入输出中查找出迷宫的两个入口，然后以这两个入口为起点做floodfill为每个点产生同入口之间距离。然后遍历整个迷宫找出距离最远的输出即可。
floodfill图论当中的基本问题，注意积累一下。

public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.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);
}
}
}
}
}

X. BFS
可以只做一次BFS, 把两个出口同时加入队列。
http://jackneus.com/programming-archives/overfencing/

不断的从“搜索点集合”中“拿出”一个点，当这个点的distance+1小于它旁边的另一个点的distance时，就跟新另一个点的distance，且把另一个点加入“搜索点集合”中。当然，这两个点必须是联通的。

直到集合为空，然后找出最大的distance

下面说明算法时间效率为O(w*h)

注意运行时间与向集合中加入点的次数成线性关系

考虑到只有一个出口时，每一个点的distance值仅会被更新一次，而有两个出口时每一个点的distance值最多被更新两次，所以每个点最多被加入集合两次，效率为O(w*h)

import java.io.*;
import java.util.*;

public class maze1
{
    private static int w, h;
    private static int[][] distance;//每个点离最近出口的距离
    private static char[][] map;//迷宫地图
    private static int longestDistance;//输出的答案
    private static LinkedList points = new LinkedList();//广度优先搜索需要搜索的点队列

    public static void main(String[] args) throws IOException
    {
        init();
        run();
        output();
        System.exit(0);
    }

    private static void run()
    {
        //当还有需要搜索的点时
        while (!points.isEmpty())
        {
            //获得当前需要搜索的点
            point p = (point)points.getFirst();
            //从队列中移除此点
            points.removeFirst();
            //分别考虑四个方向
            for (int facing = 0; facing < 4; facing++)
            {
                //如果下一步可以走且此点的distance加1小于下一点的distance(发现最优路线)
                if (canMoveAndBester(p, facing))
                {
                    //获得下一点
                    point nextPoint = move(p, facing);
                    //跟新下一点的distance
                    distance[nextPoint.x][nextPoint.y] = distance[p.x][p.y] + 1;
                    //把下一点加入搜索队列
                    points.addLast(nextPoint);
                }
            }
        }
        //计算最大的distance
        longestDistance = calcLongestDistance();
    }

    private static int calcLongestDistance()
    {
        int retDistance = 0;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                retDistance = Math.max(retDistance, distance[i][j]);
            }
        }
        return retDistance;
    }
    //如果下一点能走且从p点（当前点）走到下一点的方案更好时返回true
    private static boolean canMoveAndBester(point p, int facing)
    {
        boolean retCanMove = true;

        switch (facing)
        {
            case 0:
                //如果走到边界或此方案不是更好的或有障碍物，下面类似
                if ((p.x == 0) || (distance[p.x - 1][p.y] <= distance[p.x][p.y] + 1) || (map[p.x * 2][p.y * 2 + 1] == '-'))
                {
                    retCanMove = false;
                }
                break;
            case 1:
                if ((p.y == w - 1) || (distance[p.x][p.y + 1] <= distance[p.x][p.y] + 1) || (map[p.x * 2 + 1][(p.y + 1) * 2] == '|'))
                {
                    retCanMove = false;
                }
                break;
            case 2:
                if ((p.x == h - 1) || (distance[p.x + 1][p.y] <= distance[p.x][p.y] + 1) || (map[(p.x + 1) * 2][p.y * 2 + 1] == '-'))
                {
                    retCanMove = false;
                }
                break;
            case 3:
                if ((p.y == 0) || (distance[p.x][p.y - 1] <= distance[p.x][p.y] + 1) || (map[p.x * 2 + 1][p.y * 2] == '|'))
                {
                    retCanMove = false;
                }
                break;
        }
        return retCanMove;
    }
    //获得下一点，facing是方向，0、1、2、3分别表示上、右、下、左
    private static point move(point p, int facing)
    {
        point retPoint = null;
        switch (facing)
        {
            case 0:
                retPoint = new point(p.x - 1, p.y);
                break;
            case 1:
                retPoint = new point(p.x, p.y + 1);
                break;
            case 2:
                retPoint = new point(p.x + 1, p.y);
                break;
            case 3:
                retPoint = new point(p.x, p.y - 1);
                break;
        }
        return retPoint;
    }

    private static void init() throws IOException
    {
        BufferedReader f = new BufferedReader(new FileReader("maze1.in"));
        StringTokenizer st = new StringTokenizer(f.readLine());
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());

        map = new char[h*2+1][w * 2 + 1];
        distance = new int[h][w];
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                distance[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 0; i < h * 2 + 1; i++)
        {
            String str = f.readLine();
            for (int j = 0; j < w * 2 + 1; j++)
            {
                map[i][j] = str.charAt(j);

                if ((i == 0) && (map[i][j] == ' '))
                {
                    distance[0][(j - 1) / 2] = 1;
                    points.addLast(new point(0, (j - 1) / 2));
                }
                if ((i == h * 2) && (map[i][j] == ' '))
                {
                    distance[h - 1][(j - 1) / 2] = 1;
                    points.addLast(new point(h - 1, (j - 1) / 2));
                }
                if ((j == 0) && (map[i][j] == ' '))
                {
                    distance[(i - 1) / 2][0] = 1;
                    points.addLast(new point((i - 1) / 2, 0));
                }
                if ((j == w * 2) && (map[i][j] == ' '))
                {
                    distance[(i - 1) / 2][w - 1] = 1;
                    points.addLast(new point((i - 1) / 2, w - 1));
                }
            }
        }
        f.close();
    }

Read full article from overfencing - codetrick