uva 705 Slash Maze

近期所做题目中最好的一道，首先是比较创新不是常规的，另外需要比较好的数学功底能够洞察到一些小细节，然后转化方法貌似有很多，我自己想了很多但是都很差劲，最后实在没办法很无耻地找了解题报告，这篇解题报告感觉写得最好，我就是按照他的思路自己写的代码1A，佩服佩服此大神

解题报告 http://hi.baidu.com/lixubd/item/1fbebd2c0389700f43634a5f

算法思路都在里面了，我就不写了，我自己独立写了代码，加了很多注释，代码虽然比较多（这道题代码本来就多），然后其实不难读懂

说明一点，预处理后的矩阵行和列都翻倍了，我的代码行和列都是从1开始标号的，而那位大神的代码都是从0开始标号的，不同

有一点这里说明一下，水平和垂直的上下左右移动没什么问题，直接递归搜索就好

但是，但是，但是，就是斜向移动，左上，右上，左下，右下，四个方向，每个方向都是有两种情况，也就是有8个情况了，8中情况对当前点的横纵坐标是有要求的，有的情况要求横坐标为奇数纵坐标为偶数，有的要求横坐标偶数纵坐标奇数，有的要求横纵都是奇数，有的要求横纵都是偶数，总之这8个人情况对当前点的横纵坐标的奇偶性的要求是不同，每种情况都需要独立判断，不是统一的，至于没什么，其实只要画图出来就可以了，这里不说明白

提示一下，原始矩阵是nm（行列），一个格子输入一个斜杆，然后这个矩阵翻倍变成2n*2m，再对应一下这8中情况当前点的位置，是在偶数行呢还是奇数行呢？是在奇数列呢还是偶数列呢？然后就明白了哈哈哈哈

#include <cstdio>
#include <cstring>
#define MAX 160  //长宽最多为75，翻倍为150
bool g[MAX][MAX];
bool vis[MAX][MAX];
int n,m;  //原始长宽
int dd[9][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}}; 
//12345678表示八个方向，上下左右,左上，右上，左下，右下；
int max,ccount,c,FIND;
void input()
{
   memset(g,0,sizeof(g));
   memset(vis,0,sizeof(vis));
   for(int i=0; i<=2*m+1; i++)  //翻倍后的迷宫的上下外围不能访问
       g[0][i]=g[2*n+1][i]=1;
   for(int i=0; i<=2*n+1; i++)  //翻倍后的迷宫的左右外围不能访问
       g[i][0]=g[i][2*m+1]=1;
   for(int i=1; i<=n; i++)  //原始迷宫的i行
   {
       char s[MAX];
       scanf("%s",s+1);
       for(int j=1; j<=m; j++)
         if(s[j]=='/')
         {
            g[2*i][(2*j)-1]=1;
            g[(2*i)-1][2*j]=1;
         }
         else
         {
            g[2*i][2*j]=1;
            g[(2*i)-1][(2*j)-1]=1;
         }
   }
/*        
        for(int i=1; i<=2*n; i++)
        {
            for(int j=1; j<=2*m; j++)
                printf("%d ",g[i][j]);
            printf("\n");
        }
*/
  return ;
}

void dfs(int x ,int y)
{
  vis[x][y]=1; 
  c++;//格子数计数 
  if(x==1 || x==2*n || y==1 || y==2*m) FIND=0; 
  //如果成环的话，一定不会到达矩阵的边界，因为一定有斜杆包围起来的，到了边界不可能有斜杆包围
  //虽然不是环但是不能就此返回，一定要把这个连通分量全部搜索完，仅仅是改变FIND表示这个连通分量不是一个环

  for(int i=1; i<=8; i++)  //枚举8个可能的方向
  {
    int xx,yy;  //将要移向的格子的坐标
    xx=x+dd[i][0];
    yy=y+dd[i][1];
    if(!g[xx][yy] && !vis[xx][yy])  //新格子是可以到达的，而且没有被访问过的
    {
      if(i<=4)  //前四个方向是上下左右，不需要做什么特殊判断，直接递归
         dfs(xx,yy);
      else    //斜方向
      {
        if(i==5) //左上
        {
           if( (g[x][y-1]&&g[x-1][y-2])&& (g[x][y+1]&&g[x-1][y])&& !(x&1)&&(y&1) || 
               (g[x-1][y]&&g[x-2][y-1])&& (g[x+1][y]&&g[x][y-1])&& (x&1)&&!(y&1) )
               dfs(xx,yy);
        }
        else if(i==6)  //右上
        {
           if((g[x][y-1]&&g[x-1][y])&& (g[x][y+1]&&g[x-1][y+2])&& !(x&1)&&!(y&1) || 
              (g[x-1][y]&&g[x-2][y+1])&& (g[x+1][y]&&g[x][y+1])&& (x&1)&&(y&1) )
              dfs(xx,yy);
        }
        else if(i==7) //左下
        {
           if( (g[x][y-1]&&g[x+1][y-2])&& (g[x][y+1]&&g[x+1][y])&& (x&1)&&(y&1)|| 
               (g[x][y-1]&&g[x-1][y])&& (g[x+1][y]&&g[x+2][y-1])&& !(x&1)&&!(y&1))
                dfs(xx,yy);
        }
        else   //右下
        {
           if( (g[x][y-1]&&g[x+1][y])&& (g[x][y+1]&&g[x+1][y+2])&& (x&1)&& !(y&1) ||
               (g[x-1][y]&&g[x][y+1])&& (g[x+1][y]&&g[x+2][y+1])&& !(x&1)&& (y&1) )
               dfs(xx,yy);
        }
       }
      }
  }

  return ;
}

void solve()
{
    //dfs,每次搜索其实都搜完了一个连通分量，其实等同于图的遍历
    max=ccount=0;
    for(int i=1; i<=2*n; i++)
        for(int j=1; j<2*m; j++)
            if(!g[i][j])
                if(!vis[i][j])
                {
                    c=0;
                    FIND=1;
                    dfs(i,j);
                    if(FIND)
                    {
                        ccount++;
                        if(c>max) max=c;
                    }
                }
    return ;
}
int main()
{
    int T=0;
    while(scanf("%d%d",&m,&n) && n && m)  //先宽再长
    {
        input();
        solve();
        T++;
        printf("Maze #%d:\n",T);
        if(!ccount)
            printf("There are no cycles.\n");
        else
            printf("%d Cycles; the longest has length %d.\n",ccount,max);
        printf("\n");
    }
    return 0;
}

原文链接: https://www.cnblogs.com/scau20110726/archive/2012/11/16/2774213.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍