The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1111-Image Perimeters DFS深度优先搜索

以前做过POJ上的3620,题意大概是要你求出相邻的X有多少个,而这个题呢,则是要求你求出整个互相邻接的X所够成的周长;
我个人认为,这两道题有异曲同工之妙。
这道题和3620不同的是,我们不能将所有与X相邻的结点都压栈,而是选择X结点压栈,为什么呢?我想了想,因为此题的周长是在你考察X的基础上向四面八方试探而求出的。你最好是立足与X结点,由于对压栈元素进行了限制,那么在进入dfs递归的时候也就不用大费周章的去判断
if(visit[i][j]==0)了,因为压栈的元素必须是没有考察过的X结点;当然这只不过是基于自己的个人习惯而已,我想,即使你不判断压栈元素,应该也能做出来吧,只不过这样似乎并不符合我们的思维习惯而已;
另外做这个题目的时候还遇到了一个小问题,就是cin.ignore()的使用,再输入r,c,x,y的值之后,由于回车符不可能被整型变量吃掉,所以它会滞留在缓冲区,使得在输入字符时回车符优先进入map数组,而且每一行之后都有一个回车符,所以这个cin.ignore()的位置也是不能改变的。
当让还有个有意思的地方,就是这个题要用向量来存储考察的方向,这样的话一个循环就可以考察完所有的方向,不用费力把所有的方向都写一遍了,这是一个很不错的方法,宜借鉴之;
最后要感谢一下网路上分享代码的大牛们,正是由于参考了你们的代码才使我有所进步;

#include<iostream>
#include
<cmath>
#include
<cstdio>
using namespace std;
#define MAX 100

char map[MAX][MAX];
int visit[MAX][MAX];
int sum;
int r,c;
int path[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};



void dfs(int a,int b)
{

    visit[a][b]
=1;
    
int i;
    
for(i=0;i<8;i++)
    
{
        
int x=a+path[i][0];
        
int y=b+path[i][1];

        
if(x>=1&&x<=r&&y>=1&&y<=c)
        
{

            
if(map[x][y]=='X'&&visit[x][y]==0)
                dfs(x,y);
                
            
else if(map[x][y]=='.'&&(x==a||y==b))
            
{
                sum
++;

            }


        }

        
else if(x==a||y==b)
            sum
++;
    }


}



int main ()

{

    
int x,y;
    
int i,j;
    
while(scanf("%d%d%d%d",&r,&c,&x,&y))
    
{
        
for(i=1;i<=r;i++)
            
for(j=1;j<=c;j++)
            
{

                visit[i][j]
=0;
            }

        
        
for(i=1;i<=r;i++)
        
{
            cin.ignore();
            
for(j=1;j<=c;j++)
            
{
                scanf(
"%c",&map[i][j]);
            }


        }

        
        sum
=0;
        
if(r==0&&c==0&&x==0&&y==0)
            
break;
        dfs(x,y);
        printf(
"%d\n",sum);
    }

return 0;
}




 

posted on 2009-03-12 20:47 abilitytao 阅读(1903) 评论(1)  编辑 收藏 引用

评论

# re: POJ 1111-Image Perimeters DFS深度优先搜索 2009-07-09 11:12 非要有姓名吗

题目好像有小问题。根据题目所给的条件(没有完全封闭的内孔)也可以边界追踪的。经试验,WA。  回复  更多评论   


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