uva705--slash maze

/*这道题我原本是将斜线迷宫扩大为原来的两倍,但是在这种情况下对于在斜的方向上的搜索会变的较容易出错,所以参考了别人的思路后将迷宫扩展为原来的3倍,这样就变成一般的迷宫问题了*/

 #include"iostream"
#include"stdio.h"
#include"algorithm"
#include"cmath"
#include"string.h"
#include"ctype.h"
#include"queue"
#include"map"
#define mx 300
using namespace std;
int w,h;
int maze[mx][mx];
char m;
int dir[][]={{,},{-,},{,},{,-}};
int visited[mx][mx];
int cnt;//记录圈的个数
int mxlen;//记录最长圈的长度
int len;//记录当前圈的长度
int flag;//标记是否构成圈
bool judge(int x,int y)
{
if(x>=&&x<*h&&y>=&&y<*w) return true;//判断点是否出界
else return false;
}
void dfs(int x,int y)
{
int k,dx,dy;
for(k=;k<;k++)
{
dx=x+dir[k][];
dy=y+dir[k][];
if(judge(dx,dy))
{
if(!visited[dx][dy]&&!maze[dx][dy])
{
visited[dx][dy]=;
len++;
dfs(dx,dy);
}
}
else //边界上的点肯定不构成圈。。。
{flag=;}
// cout<<len<<endl;
}
}
int main()
{
int i,j,k;
int count1=;
while(cin>>w>>h,w||h)
{
count1++;
memset(maze,,sizeof(maze));
for(i=;i<h;i++)
{
getchar();
for(j=;j<w;j++)
{
scanf("%c",&m);
if(m=='/')
{
maze[*i+][*j]=;maze[*i+][*j+]=;maze[*i][*j+]=;
}
else
{
maze[*i][*j]=;maze[*i+][*j+]=;maze[*i+][*j+]=;
}
}
}
for(i=;i<*h;i++)
for(j=;j<*w;j++)
{visited[i][j]=maze[i][j];}
mxlen=;
cnt=;
for(i=;i<*h;i++)
{
for(j=;j<*w;j++)
{
if(maze[i][j]==&&!visited[i][j])
{
len=;
flag=;
visited[i][j]=;
dfs(i,j);
if(flag)
{
cnt++;
if(len>mxlen) mxlen=len;
}
}
}
}
cout<<"Maze #"<<count1<<":"<<endl;
if(cnt==) cout<<"There are no cycles."<<endl<<endl;
else
cout<<cnt<<" Cycles; "<<"the longest has length "<<mxlen/<<'.'<<endl<<endl;
}
return ;
}
上一篇:ajax用户是否存在


下一篇:Windows系统下Memcached缓存系列一:Couchbase(服务器端)和CouchbaseClient(c#客户端)的安装教程