分支限界之迷宫问题求解
已知某矩形迷宫如下图所示。其中“\”和“/”表示围墙。图中从一个方格出发在没有围墙阻挡的情况下可进入另一个方格，最后回到开始的方格，这样就构成了一个回路。设回路的长度为方格的数量，请编写算法求图中回路的最大长度。下图中的回路的最大长度为16。
输入：
输入的第一行包含两个整数w和h，也就是迷宫的宽度和高度。其后的h行，每行包含w个字符，分别是“\”和“/”，代表迷宫中的围墙。
输出：
输出两个整数，中间用空格隔开，分别是该矩形中有多少个回路，以及最长回路的长度。
样例输入：
6 4
//\/
////
//\/
////
样例输出：
2 16
要求：
（1）写出采用分支限界法求解上述问题的算法，并分析算法的时间复杂度。
（2）画出采用分支限界法求解样例输入时的解空间树和搜索空间树，并给出搜索空间树中每个结点的变量定义以及对应的值。
（3）根据（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;
}
这个需要具体学习相关树的内容，自己学懂才是真的属于自己的哦
深度优先遍历。