UVa 705 - Slash Maze, 斜线迷宫

705-Slash Maze

4016

40.19%

1120

83.66%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=646

题目类型： 搜索

题目：

By filling a rectangle with slashes (/) and backslashes (), you can generate nice little mazes. Here is an example:

As you can see, paths in the maze cannot branch, so the whole maze only contains cyclic paths and paths entering somewhere and leaving somewhere else. We are only interested in the cycles. In our example, there are two of them.

Your task is to write a program that counts the cycles and finds the length of the longest one. The length is defined as the number of small squares the cycle consists of (the ones bordered by gray lines in the picture). In this example, the long cycle has length 16 and the short one length 4.

题目大意翻译：

用斜线和反斜杠来填写一个矩形,您可以生成漂亮的小迷宫。这里有一个例子:

如上图，可以组成一个迷宫，斜线和反斜杠相当于是迷宫的墙，路径在迷宫中不能分支， 所以整个迷宫只包含循环路径封闭（无法走出迷宫），

还有的路径是通向迷宫外面的。

你的任务是写一个程序， 计算出所形成的迷宫有多少个封闭路径（循环路径），以及计算出其中最长的封闭路径有多长。\

样例输入：

6 4
\//\\/
\///\/
//\\/\
\/\///
3 3
///
\//
\\\
0 0

样例输出：

Maze #1:
2 Cycles; the longest has length 16.

Maze #2:
There are no cycles.

分析与总结：

初看这题时，有点无所适从，主要是所给的图像并不是按常规、方格是斜着放的，这样的话，比较难转换成用数组来存。

后来，我发现题目所给的斜杆的长度是一个格子长的两倍，于是，便很自然的想到把原来的图像扩大两倍，在数组中用两个格子来存储一根斜线。

这样的话，就可以用数组来表示这个图像。

转换后的图如下（画得有点搓）

其中，五角星代表的格子数组中是空的（可以用一个符号来表示），这些格子是可以走的。

转换后，就可以很简单的用搜索做出这道题了。

其中需要注意的地方： 搜索时，可以往8个方向走，其中，往上、下、左、右走时，如果那个格子为空的，那么就可以直接走过去。

但是如果往斜着方向走时，仅仅是空的还不足以判断可以走，还需要再特判。

例如， 会出现如下情况：

这里从左上往右下走（或者从右下往左上走）时，虽然右下是空的，但是不可以走， 因为有斜杆”墙”阻挡着。

除了这种方法，还可以模拟光线反射的路径来做这题（我队友想到的就是这种方法），但是代码写起来的话会更难。

还有一种方法就是1格转换成9格，这种方法只要转换好之后， 搜索写起来是最容易的，因为不需要特判情况。

下面是1格转4格的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int w,h, last_x, last_y;
char str[100][100], map[300][300];
int dir[8][2]={{1,0}, {-1,0}, {0,1},{0,-1}, // 这一行是上下左右方向走
               {-1,1},{1,1},{1,-1},{-1,-1}}; // 这一行是斜的方向走，从左上开始，顺时针

bool vis[300][300];

// 把输入进行转换
void change(int row){
    for(int i=0; i<strlen(str[row]); ++i){
        int m_row=row*2, m_col=i*2;
        if(str[row][i] == '\\' ){
            map[m_row][m_col] = '\\';
            map[m_row+1][m_col+1] = '\\';
            map[m_row][m_col+1] = ' ';
            map[m_row+1][m_col] = ' ';  
        }
        else if(str[row][i] == '/'){
            map[m_row][m_col+1] = '/';
            map[m_row+1][m_col] = '/';
            map[m_row][m_col] = ' ';
            map[m_row+1][m_col+1] = ' ';  
        }
    }
}

// 如果是斜着走，还要进行特判能否走
bool isPass(int x, int y, int dirNo){
    int x1,y1,x2,y2;  // x1为同row, x2为同col
    x1 = x, y1=y+dir[dirNo][1];
    x2 = x+dir[dirNo][0], y2=y;

    if(dirNo==4 || dirNo==6){
        if(map[x1][y1]=='/' && map[x2][y2]=='/')
            return true;
    }
    else{
        if(map[x1][y1]=='\\' && map[x2][y2]=='\\')
            return true;
    }
    return false;
}
 

void dfs(int x,int y,int &cnt){
    for(int i=0; i<8; ++i){
        int dx=x+dir[i][0], dy=y+dir[i][1];
        if(i<4) { // 如果是往上，下，左，右走
            if(dx>=0 && dx<2*h && dy>=0 && dy<2*w && map[dx][dy]!='\\'&&map[dx][dy]==' ' && map[dx][dy]!='/' && !vis[dx][dy]){
                vis[dx][dy] = true;
                last_x = dx, last_y = dy;  // 记住最后一个入栈的位置
                ++cnt;
                dfs(dx,dy,cnt);
            }
        }
        else{ // 如果是往斜的方向走
            if(dx<0 || dx>=2*h || dy<0 || dy>=2*w || map[dx][dy]=='\\' || map[dx][dy]=='/' || vis[dx][dy])
                continue;
            if(isPass(x,y,i)){
                vis[dx][dy] = true;
                ++cnt;
                last_x = dx, last_y = dy;
                dfs(dx, dy, cnt);
            }
        }
    } 
}

int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    int cas=1;
    while(~scanf("%d %d%*c",&w, &h) && w && h){
        memset(str, 0, sizeof(str));
        memset(map, 0, sizeof(map));
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<h; ++i){
            gets(str[i]);
            change(i);
        }
        int maxNum=-2147483646, cnt, circleNum=0;
        bool haveCircle = false;

        for(int i=0; i<2*h; ++i){
            for(int j=0; j<2*w; ++j){
                if(map[i][j]==' ' && !vis[i][j]){
                    map[i][j] = '#';
                    cnt=1;
                    vis[i][j] = true;
                    dfs(i,j,cnt);
                    // 判断是否是环的，首先要判断结束的那点是否和开始的相邻
                    bool flag = false;
                    for(int k=0; k<8; ++k){
                        int dx=last_x+dir[k][0];
                        int dy=last_y+dir[k][1];
                        if(dx==i && dy==j){ 
                            flag=true; break;
                        }
                    }
                    // 相邻的还不够，数量至少是4才能形成环状
                    if(flag && cnt>=4){
                        haveCircle = true;
                        ++circleNum;
                        if(cnt > maxNum)
                            maxNum = cnt;
                    }
                }

            }
        }
        printf("Maze #%d:\n",cas++);

        if(haveCircle){
            printf("%d Cycles; the longest has length %d.\n\n", circleNum, maxNum);
        }
        else{
            printf("There are no cycles.\n\n");
        }  
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double