题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=646
先将每个格子划分为3*3的小格，斜杠占据的小格标记为1，其它的为0。然后遍历即可。
#include <cstdio>
#include <cstring>
int row, col;
int map[230][230];
bool vis[230][230];
int cnt, curLen, maxLen;
bool iscyc;
void dfs(int r, int c)
{
if(r < 0 || r >= row || c < 0 || c >= col)
{
iscyc = false; // 由于没有分枝，所以能走出图就一定不会构成环。
return;
}
if(map[r][c] || vis[r][c])
return;
vis[r][c] = true;
++curLen;
dfs(r -1, c);
dfs(r, c + 1);
dfs(r + 1, c);
dfs(r, c - 1);
}
int main()
{
char ch;
int ca = 0;
while(EOF != scanf("%d%d", &col, &row) && (col || row))
{
row *= 3;
col *= 3;
memset(map, 0, sizeof(map));
memset(vis, 0, sizeof(vis));
for(int i = 0; i < row; i += 3)
{
getchar();
for(int j = 0; j < col; j += 3)
{
scanf("%c", &ch);
if(ch == '/')
{
map[i][j + 2] = 1;
map[i + 1][j + 1] = 1;
map[i + 2][j] = 1;
}
else if(ch == '\\')
{
map[i][j] = 1;
map[i + 1][j + 1] = 1;
map[i + 2][j + 2] = 1;
}
}
}
cnt = 0;
maxLen = 0;
for(int i = 0; i < row; ++i)
for(int j = 0; j < col; ++j)
{
if(!map[i][j] && !vis[i][j])
{
iscyc = true;
curLen = 0;
dfs(i, j);
if(iscyc)
{
++cnt;
if(curLen > maxLen)
maxLen = curLen;
}
}
}
printf("Maze #%d:\n", ++ca);
if(cnt)
printf("%d Cycles; the longest has length %d.\n\n", cnt, maxLen / 3);
else
printf("There are no cycles.\n\n");
}
return 0;
}
posted on 2012-01-03 14:46
wuxu 阅读(361)
评论(0) 编辑 收藏 引用 所属分类:
搜索