uva705 - Slash Maze 【转化+dfs】

电玩女神 2022-08-12 01:02 85阅读 0赞

题目：[uva705 - Slash Maze ][uva705 - Slash Maze]

题意：给出一个迷宫，看题目给出的图就知道，由 \\ 和 / 组成，让你求有几个环，然后最大的环由几个矩形组成。

分析：这是一道很灵活的题目，关键在于对题目给出图形的转化，例如‘ \\ ’ 可以转化为

1 0 0

0 1 0

0 0 1

而‘ / ' 可以转化为

0 0 1

0 1 0

1 0 0

然后直接广搜或者深搜都可以，找环就可以了。也可以转化为 2 \* 2 的，需要特判。

AC代码：

#include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <cstring>
    #include <utility>
    #include <cmath>
    #include <iostream>
    #include <string>
    #include <cctype>
    using namespace std;
    const int N = 3*100;
    int cas,tmp;
    bool ok;
    int mp[N][N];
    int m,n;
    int dfs(int x,int y)
    {
        mp[x][y]=1;
        tmp++;
        if(x==0 || x==(3*m-1) || y==0 || y==(3*n-1))
            ok=true;
        if(x>0 && mp[x-1][y]==0) dfs(x-1,y);
        if(y>0 && mp[x][y-1]==0) dfs(x,y-1);
        if(x<(3*m-1) && mp[x+1][y]==0) dfs(x+1,y);
        if(y<(3*n-1) && mp[x][y+1]==0) dfs(x,y+1);
    }
    int main()
    {
        int T=1;
        while(~scanf("%d%d",&n,&m))
        {
            if(n==0 && m==0)
                break;
            memset(mp,0,sizeof(mp));
            for(int i=0;i<m;i++)
            {
                string s;
                cin>>s;
                for(int j=0;j<s.size();j++)
                {
                    if(s[j]=='/')
                    {
                        mp[3*i][3*j+2]=1;
                        mp[3*i+1][3*j+1]=1;
                        mp[3*i+2][3*j]=1;
                    }
                    else if(s[j]=='\\')
                    {
                        mp[3*i][3*j]=1;
                        mp[3*i+1][3*j+1]=1;
                        mp[3*i+2][3*j+2]=1;
                    }
                }
            }
            int ans=0;
            cas=0,tmp=0,ok=false;
            for(int i=0;i<3*m;i++)
            {
                for(int j=0;j<3*n;j++)
                {
                    if(mp[i][j]==0)
                    {
                        dfs(i,j);
                        if(ok==false){
                            ans=max(tmp,ans);
                            cas++;
                        }
                        ok=false;
                        tmp=0;
                    }
                }
            }
            printf("Maze #%d:\n",T++);
            if(cas==0)
                printf("There are no cycles.\n");
            else
                printf("%d Cycles; the longest has length %d.\n",cas,ans/3);
            printf("\n");
        }
        return 0;
    }

[uva705 - Slash Maze]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=646