随笔-68  评论-10  文章-0  trackbacks-0

题目链接: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, 
0sizeof(map));
        memset(vis, 
0sizeof(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 阅读(337) 评论(0)  编辑 收藏 引用 所属分类: 搜索

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理