注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

UVA 705 Slash Maze  

2012-07-03 14:34:22|  分类: 数据结构基础 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
= =看到这题,第一反应就是没思路。'/'和'\'输入后应该用什么表示。
一开始我是想把'/'用  #* 存入,把'\'用 *# 存入。 再去求#的连通块。
            *#                      #*
但是对于边界的处理有点迷茫。

UVA 705 Slash Maze - Minary - Minary_Acdream看了其他人的题解,他们有两种方法,分别是用2*2的数组表示'\'和'/',和用3*3 的数组表示
我用的是2*2的,将
\//\\/ \///\/ //\\/\ \/\///
将'/'用 1 存储,'\'用 2 存储,其他用 0 ,即为:
200101202001
021010020210
200101012001
021010100210
010120200120
101002021002
200120010101
021002101010

接着就是处理边界问题,用到了floodfill算法,这算法归根结底还是DFS。

将在边界的0和与边界0相连的0都处理成为3,即:
注意:
在走的过程需要依据当前相邻的正反斜线决定可行的方向。
 
233131232331
321310023213
233101012331
321010100213
310120200123
101002021332
200120013131
321332131313

此时在去找0的连通块,找到几块既有几个圈,再去记录它们的长度,输出最大值即可。

下面是我的代码:

#include<iostream>
#include<string.h>
using namespace std;

int map[1000][1000];
int dir[8][2] = {{-1, -1},{-1, 0},{-1, 1},{0, -1},{0, 1},{1, -1},{1, 0},{1, 1}};
int n,m;
int length;
int N = 0;
void DFS(int x,int y)
{
 int i,xx,yy;
 map[x][y] = 3;
 length ++;
 for(i = 0;i < 8;i ++)
 {
  xx = x + dir[i][0];
  yy = y + dir[i][1];
  if(xx < 0 || yy < 0 || xx >= 2 * n || yy >= 2 * m)  continue;
  if(map[xx][yy] == 0)
  {
  if (xx == x || yy == y) DFS(xx,yy);
  else
  {
   if(i == 0) if(map[x][y - 1] != 1) DFS(xx,yy);
   if(i == 7) if(map[x][y + 1] != 1) DFS(xx,yy);
   if(i == 5) if(map[x][y - 1] != 2) DFS(xx,yy);
   if(i == 2) if(map[x][y + 1] != 2) DFS(xx,yy);
  }
 
  }
 }
}


int main()
{
 bool E;
 char a;
// int n,m;
 while(cin>>m>>n)
 {
  if(n == 0 && m == 0)break;

  for(int i = 0;i < n;i ++)  
  { 
   for(int j = 0;j < m;j++)   
   {  
    cin>>a;
    E = (a == '\\');
    map[i * 2][j * 2] = E ? 2 : 0;
    map[i * 2][j * 2 + 1] = E ? 0 : 1;
    map[i * 2 + 1][j * 2] = E ? 0 : 1;
    map[i * 2 + 1][j * 2 + 1] = E ? 2 : 0;
   
   }
   
  }
  
  // 处理矩阵周边的 0。
  for (int i = 0; i < n * 2; i++)
  {
   for (int j = 0; j < m * 2; j++)   
   {
    if (map[i][j] == 0)
    if (i == 0 || j == 0 || i == (n * 2- 1) || j == (m * 2- 1))   DFS(i,j);
      
   }
  }
  
    
  int max = 0, cycles = 0;  
  for (int i = 0; i < n * 2; i++)
  {
   for (int j = 0; j < m * 2; j++)
    if (map[i][j] == 0)
    {
     cycles++;
     length = 0;
     DFS(i,j);
    if (max < length)
     max = length;
    }
  }     
    
  cout << "Maze #" << ++N << ":" << endl;
  if (max > 0)
   cout << cycles<<" Cycles; the longest has length "<<max<<".";

  else
   cout << "There are no cycles.";
  cout << endl << endl;
  
 } 
}

  评论这张
 
阅读(456)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018