OJ-迷宫探索（在迷宫中找出最长环路的长度）

1、题目简述：

在迷宫中找出最长环路的长度，不是找到出路。

详细描述：

迷宫是由一系列方格组成一个矩形区域，下图是一个 4 * 6 的迷宫 

每个方格中都有一条红色的斜线（/或者\），这是墙，无法通过。灰线不是墙，可自由跨越。 

在迷宫内，只能在相邻的（有公共边的才算相邻，公共顶点不算）三角形的区域之间相互移动。左上角灰色三角形，就是一个区域，从这个区域，可以移动到下面黄色三角形区域中。 

不能越界，只能在大的矩形范围内移动。左边紫色这种移动方式，是不允许的。 

可以看到，中间蓝色的分别是两条环路，环路长度指的是走完这条环路需要走过的三角区域个数，两条环路的长度分别是16和4；绿色的不是一条环路。

请实现如下接口

/* 功能：找出一个迷宫中的最长环路长度，以及总的环路个数

 * 输入：存放迷宫信息的记事本文件路径，该程序从文件中读取迷宫信息。该文件格式后面会说明

 * 输出：CycleCount，环路个数，上面的迷宫，CycleCount为2

* 返回：最长环路长度，上面的迷宫，应返回16.如果没有环路，返回-1.

 */

int FindLongestCycle(constchar* mazefile, int*CycleCount)

{

    /* 请实现*/

    return 0;

} 

迷宫信息：

本题例子中的迷宫以下面文本格式保存。其中斜线，则表示对应方格中的墙。斜线之间无空格。左边的字符串中的斜线和右边图画中的墙一一对应。

随题目附带的两个用例，在testcase目录下。

每行结束以回车（”\r\n”）收尾，没有多余的空格。

最后一行结束，没有回车。

解题时，无需检查该文件格式，由用例保证格式正确。

 

约束：

环路都是简单环路。即除了第一个顶点和最后一个顶点外，其余顶点不重复出现的环路。不会有“8”字形，“6”字型这样的环路。

迷宫宽和高不超过50，宽和高均大于1.

每个格子里都有一堵墙（也就是都会被填进一个斜线），不会出现空格子；

墙只有两种（/ 和 \），不会有其他类型。

2、解题思路：
http://blog.csdn.net/ra_winding/article/details/7724290

经典的斜线迷宫题。

可用 FloodFill 解决。

首先知道，没有封闭的路径，必然将通往图的外面。

所以只要从图的边界开始 FloodFill，把不满足条件的排除后。

再对每一个点去 FloodFill 即可求出所要的解。

而对于斜线的处理，有三种方法：

1. 九分法：将所有的格子都扩大成 9 * 9 的格子，例如

‘/’ 就会变成

然后只要用普通的 FloodFill 对每格上下左右四个方向的 DFS 就可以。

2. 四分法：将所有的格子扩大成 4 * 4 的格子，例如

‘/’ 就会变成

然后依然是对每个格子向八个方向 FloodFill ，但是要注意，在 2 * 2 格子中的某点向周围Flood 的时候，只能到达上下左右的 2 * 2格子。

反之如果 FloodFill 后依然在原先的 2 * 2格子，或者对角线方向的 2 * 2 格子的，将会是穿过了 '/' 的非法情况，需要排除掉。

3. 光线反射法：模拟一条光线在迷宫中照射，继续看图：

对于每个格子，光线可能从四个方向射进来。

在 FloodFill 的时候，判断光线来的方向，找到下一个 FloodFill 的格子即可。

三种方法，第一种较为简单，但是要将原图长宽各扩大三倍，得到一张原图九倍大的新图。

而第二种方法，只要将原图扩大四倍，但是要判断要FloodFill的格子是否可以FloodFill。

而第三种方法，较为复杂，对光线进来的四个方向都要判断反射出去的方向，可以用一个 enum 配合 const 数组来映射，好处就是不用扩大原图，时间复杂度相对前两种，常数较低。

3、代码

#include "Maze.h"

/* 功能：找出一个迷宫中的最长环路以及环路个数
 * 输入：存放迷宫信息的记事本文件路径，该程序从文件中读取迷宫信息。
 * 输出：CycleCount，环路个数
 * 返回：最长环路长度,如果没有环路，返回-1.
 */

#include <cstdio>
#include <cstring>


enum Direction {
    UP = 0,
    DOWN = 1,
    LEFT = 2,
    RIGHT = 3,
};

struct Change {
    int x;
    int y;
};

const Direction DIRECTION[] = {
    UP,
    DOWN,
    LEFT,
    RIGHT,
};
// Form four directions what are UP, DOWN, LEFT, RIGHT.
const Change CHANGE[] = {
    {-1, 0},
    { 1, 0},
    { 0, -1},
    { 0, 1},
};

// Form four directions what are UP, DOWN, LEFT, RIGHT.
const Direction REFLEX_SLASH[] = {
    LEFT,
    RIGHT,
    UP,
    DOWN,
};
const Direction REFLEX_BACKSLASH[] = {
    RIGHT,
    LEFT,
    DOWN,
    UP,
};

const int LIMITS_W = 100;
const int LIMITS_H = 100;

int num_case = 0;

char maze[LIMITS_W][LIMITS_H];
int w, h;

bool is_visited[LIMITS_W][LIMITS_H][4];

Direction Opposite(Direction direction);
int FloodFill(int x, int y, Direction direction);

Direction Opposite(Direction direction) {
    if (direction == LEFT) {
        return RIGHT;
    } else
    if (direction == RIGHT) {
        return LEFT;
    } else
    if (direction == UP) {
        return DOWN;
    } else
    if (direction == DOWN) {
        return UP;
    }
}

int FloodFill(int x, int y, Direction direction) {
    // Exit.
    if (x < 0 || x >= h
     || y < 0 || y >= w) {
        return 0;
    }
    if (is_visited[x][y][direction]) {
        return 0;
    }
    is_visited[x][y][direction] = true;
    // Continue.
    Direction direction_leave;
    if (maze[x][y] == '/') {
        direction_leave = REFLEX_SLASH[direction];
    } else {
        direction_leave = REFLEX_BACKSLASH[direction];
    }
    is_visited[x][y][direction_leave] = true;
    return 1 + FloodFill(x + CHANGE[direction_leave].x,
                         y + CHANGE[direction_leave].y,
                         Opposite(direction_leave));
}

int FindLongestCycle(const char* mazefile, int *CycleCount)
{

    if (mazefile == NULL || NULL == CycleCount)
    {
        return -1;
    }
    int i = 0;
    FILE* pFile = fopen(mazefile,"r");
    while (fgets(maze[i],LIMITS_W,pFile) != NULL)
    {
        i++;
    }
    fclose(pFile);
    h = i;
    w = strlen(maze[0])-1;

    // DFS: Remove grids of the maze without cycles.
    memset(is_visited, false, sizeof(is_visited));
    for (int i = 0; i < h; ++i)
    {
        FloodFill(i, 0, LEFT);
        FloodFill(i, w - 1, RIGHT);
    }
    for (int i = 0; i < w; ++i)
    {
        FloodFill(0, i, UP);
        FloodFill(h - 1, i, DOWN);
    }
    //Show();
    // DFS: Search and compete the maze with cycles.
    int max = 0;
    int sum = 0;
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            for (int k = 0; k < 4; k++)
            {
                int result = FloodFill(i, j, DIRECTION[k]);
                if (result)
                {
                    max = result > max ? result : max;
                    ++sum;
                }
            }
        }
    }
    // Outputs.
    if (sum)
    {
        printf("%d Cycles; the longest has length %d.\n", sum, max);
        *CycleCount = sum;
        return max;
    }
    else
    {
        return -1;
    }
}