分支限界之迷宫问题求解

Question

已知某矩形迷宫如下图所示。其中“\”和“/”表示围墙。图中从一个方格出发在没有围墙阻挡的情况下可进入另一个方格，最后回到开始的方格，这样就构成了一个回路。设回路的长度为方格的数量，请编写算法求图中回路的最大长度。下图中的回路的最大长度为16。

输入：
输入的第一行包含两个整数w和h，也就是迷宫的宽度和高度。其后的h行，每行包含w个字符，分别是“\”和“/”，代表迷宫中的围墙。
输出：
输出两个整数，中间用空格隔开，分别是该矩形中有多少个回路，以及最长回路的长度。
样例输入：
6 4
//\/
////
//\/
////
样例输出：
2 16
要求：
（1）写出采用分支限界法求解上述问题的算法，并分析算法的时间复杂度。
（2）画出采用分支限界法求解样例输入时的解空间树和搜索空间树，并给出搜索空间树中每个结点的变量定义以及对应的值。
（3）根据（1）中的算法编写程序。

Answer 1

*
dfs判断环，建图需要技巧，图变成了三维的(h * w * 2)第三维的2用来表示一个格子被'/'或者'/'分
成的两块

核心就是判断环，但是由于这题特殊性使得判断环比较简单；利用分别遍历h * w * 2个点，遍历到的点
设置为visited, 当遇到遍历初始点时且这个初始点不是前驱则表示找到一条环

注意一定要判断是否是前驱，否则会产生判断错误
*/

#include <iostream>
#include <memory>
#define MAX_N 75
#define MAX_T 150
using namespace std;

bool visited[MAX_N + 5][MAX_N + 5][2];
char input[MAX_N + 5][MAX_N + 5];
int w, h, cyNum, lCy = INT_MIN;
int startH, startW, startP;

bool inRange(int curH, int curW)
{
    return (curH >= 1 && curH <= h && curW >= 1 && curW <= w);
}

void dfs(int preH, int preW, int preP, int curH, int curW, char type, int which, int length)
{
    //cout<<curH<<" "<<curW<<" "<<which<<endl;
    
    visited[curH][curW][which] = true;
    if(type == '//')
    {
        if(which == 0)
        {
            if(inRange(curH, curW - 1))
            {
                //visited[curH][curW - 1][1] = true;
                if(input[curH][curW - 1] == '//')
                {
                    if(!visited[curH][curW - 1][1])
                        dfs(curH, curW, which, curH, curW - 1, '//', 1, length + 1);
                    if(!(curH == preH && curW - 1 == preW && preP == 1) && curH == startH && curW - 1 == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH][curW - 1] == '/')
                {
                    if(!visited[curH][curW - 1][1])
                        dfs(curH, curW, which, curH, curW - 1, '/', 1, length + 1);
                    if(!(curH == preH && curW - 1 == preW && preP == 1) && curH == startH && curW - 1 == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
            if(inRange(curH + 1, curW))
            {
                if(input[curH + 1][curW] == '//')
                {
                    if(!visited[curH + 1][curW][1])
                        dfs(curH, curW, which, curH + 1, curW, '//', 1, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 1) &&curH + 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH + 1][curW] == '/')
                {
                    if(!visited[curH + 1][curW][0])
                        dfs(curH, curW, which, curH + 1, curW, '/', 0, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 0) && curH + 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
        else if(which == 1)
        {
            if(inRange(curH, curW + 1))
            {
                //visited[curH][curW + 1][0] = true;
                if(input[curH][curW + 1] == '//' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '//', 0, length + 1);
                else if(input[curH][curW + 1] == '/' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '/', 0, length + 1);
                if(!(curH == preH && curW + 1 == preW && preP == 0) && curH == startH && curW + 1 == startW && startP == 0)
                {
                    cyNum++;
                    if(length > lCy)
                        lCy = length;
                }
            }
            if(inRange(curH - 1, curW))
            {
                if(input[curH - 1][curW] == '//')
                {
                    if(!visited[curH - 1][curW][0])
                        dfs(curH, curW, which, curH - 1, curW, '//', 0, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 0) && curH - 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH - 1][curW] == '/')
                {
                    if(!visited[curH - 1][curW][1])
                        dfs(curH, curW, which, curH - 1, curW, '/', 1, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 1) && curH - 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
    }
    else if(type == '/')
    {
        if(which == 0)
        {
            if(inRange(curH, curW - 1))
            {
                if(input[curH][curW - 1] == '//' && !visited[curH][curW - 1][1])
                    dfs(curH, curW, which, curH, curW - 1, '//', 1, length + 1);
                else if(input[curH][curW - 1] == '/' && !visited[curH][curW - 1][1])
                    dfs(curH, curW, which, curH, curW - 1, '/', 1, length + 1);
                if(!(curH == preH && curW - 1 == preW && preP == 1) && curH == startH && curW - 1 == startW && startP == 1)
                {
                    cyNum++;
                    if(length > lCy)
                        lCy = length;
                }
            }
            if(inRange(curH - 1, curW))
            {
                if(input[curH - 1][curW] == '//')
                {
                    if(!visited[curH - 1][curW][0])
                        dfs(curH, curW, which, curH - 1, curW, '//', 0, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 0) && curH - 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH - 1][curW] == '/')
                {
                    if(!visited[curH - 1][curW][1])
                        dfs(curH, curW, which, curH - 1, curW, '/', 1, length + 1);
                    if(!(curH - 1 == preH && curW == preW && preP == 1) && curH - 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
        else if(which == 1)
        {
            if(inRange(curH, curW + 1))
            {
                if(input[curH][curW + 1] == '//' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '//', 0, length + 1);
                else if(input[curH][curW + 1] == '/' && !visited[curH][curW + 1][0])
                    dfs(curH, curW, which, curH, curW + 1, '/', 0, length + 1);
                if(!(curH == preH && curW + 1 == preW && preP == 0) && curH == startH && curW + 1 == startW && startP == 0)
                {
                    cyNum++;
                    if(length > lCy)
                        lCy = length;
                }
            }
            if(inRange(curH + 1, curW))
            {
                if(input[curH + 1][curW] == '//')
                {
                    if(!visited[curH + 1][curW][1])
                        dfs(curH, curW, which, curH + 1, curW, '//', 1, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 1) && curH + 1 == startH && curW == startW && startP == 1)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
                else if(input[curH + 1][curW] == '/')
                {
                    if(!visited[curH + 1][curW][0])
                        dfs(curH, curW, which, curH + 1, curW, '/', 0, length + 1);
                    if(!(curH + 1 == preH && curW == preW && preP == 0) && curH + 1 == startH && curW == startW && startP == 0)
                    {
                        cyNum++;
                        if(length > lCy)
                            lCy = length;
                    }
                }
            }
        }
    }
}

int main()
{
    int i, j, seq = 0;
    while(cin>>w>>h && !(w == 0 && h == 0))
    {
        seq++;
        getchar();
        for(i = 1; i <= h; i++)
        {
            for(j = 1; j <= w; j++)
                input[i][j] = getchar();
            getchar();
        }
        memset(visited, 0, sizeof(visited));
        cyNum = 0;
        lCy = INT_MIN;
        for(i = 1; i <= h; i++)
        {
            for(j = 1; j <= w; j++)
            {
                for(int k = 0; k < 2; k++)
                {
                    if(i == 1 && j == 3 && k == 1)
                    {
                        int a = 2;
                    }
                    startH = i, startW = j, startP = k;
                    if(!visited[i][j][k])
                        dfs(-1, -1, -1, i, j, input[i][j], k, 1);
                }
            }
        }
        cout<<"Maze #"<<seq<<":"<<endl;
        if(cyNum != 0)
            cout<<cyNum<<" Cycles; the longest has length "<<lCy<<"."<<endl;
        else
            cout<<"There are no cycles."<<endl;
        cout<<endl;
    }
    return 0;
}