http://poj.org/problem?id=1103
#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;
}
