HDU - 1241 - Oil Deposits(DFS联通块)

题目链接

题意：

就是给你一个地图，找出所有不相连（八个方向）的@组合有多少个

题解：

经典的DFS求联通块的题，和紫书上求油田一样，枚举每一个点进行DFS搜联通的@

AC代码：

#include <stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
char mat[maxn][maxn];
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
int  m,n;
int sum;
void Dfs(int x,int y){
    int tx;
    int ty;
    for(int i=0;i<8;i++){
        tx=x+dir[i][0];
        ty=y+dir[i][1];
        if(1<=tx&&tx<=m&&1<=ty&&ty<=n){//注意！对于二维数组来说，x行y列，意味着x是纵向坐标，y是横向坐标
            if(mat[tx][ty]=='@'){
                mat[tx][ty]='*';
                Dfs(tx,ty);
            }
        }
    }
}
int main(){
    while(scanf("%d%d",&m,&n)){
        if(m==0&&n==0){
            break;
        }
        //memset(mat,0,sizeof(mat));
        sum=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //scanf("%s",mat[i]+1);
                cin>>mat[i][j];
                //scanf("%c",&mat[i][j]);
            }
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(mat[i][j]=='@'){
                    sum++;
                    mat[i][j]='*';
                    Dfs(i,j); //深搜，消除同一连通块的所有油田标记
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}