首页 > 其他 > 详细

单纯的dfs

时间:2016-03-26 15:19:55      阅读:132      评论:0      收藏:0      [点我收藏+]

此类题是dfs中最简单的题,如果要求类似于次数,多少种方法的问题,还要加上回溯法(恢复现场等),(n皇后剪枝)

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=105;
char a[maxn][maxn];
int lie[8][2]= {{-1,1},{0,1},{1,1},{-1,0},{1,0},{-1,-1},{1,-1},{0,-1}};//二维数组存储方向
int visit[maxn][maxn];
int n,m;
void dfs(int x,int y)          //将图遍历一次即可
{
    for(int i=0; i<8; i++)
    {
        int dx=x+lie[i][0];
        int dy=y+lie[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&a[dx][dy]==@&&!visit[dx][dy])
        {
            visit[dx][dy]=1;
            dfs(dx,dy);
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m)
    {
        memset(visit,0,sizeof(visit));
        for(int i=0; i<n; i++)
        {
            scanf("%s",a[i]);
        }
        int count=0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(a[i][j]==@&&!visit[i][j])
                {
                    ++count;
                    dfs(i,j);
                }
            }
        }
        cout<<count<<endl;
    }
    return 0;
}

 

单纯的dfs

原文:http://www.cnblogs.com/calmwithdream/p/5322851.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!