hdu 2952 Counting Sheep（簡單dfs）

Counting Sheep

題目連結： 點選打開連結

題目大意：T組資料，每組資料第一行兩個數H、W，H行W列包含 “.”草地 或 “#”羊 ，問有多少羊群（一隻羊的上下左右四個方向如果有羊則算是一個羊群）。

解題思路：簡單dfs周遊搜尋，從第一個字元開始，如果判斷是羊，羊群數tot++,并且對這隻羊進行dfs(把其上下左右的羊都标記為草，因為這隻算一個羊群),再進行下一個字元判斷。

代碼如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 105
char map[N][N];
int go[4][2]={0,1,0,-1,1,0,-1,0};///四個方向判斷
int m,n;
void dfs(int s,int t){
    if(map[s][t]=='.') return ;///碰到不是羊，則結束此次搜尋
    map[s][t]='.';///開始對這隻羊搜尋，将這隻羊标記為草
    for(int i=0;i<4;i++){
        int x=s+go[i][0],y=t+go[i][1];
        if(x>=0&&x<m&&y>=0&&y<n&&map[x][y]=='#'){ ///如果旁邊的依舊是羊，繼續搜尋
            dfs(x,y);
        }
    }
}

int main(){
    int ca;
    scanf("%d",&ca);
    while(ca--){
        scanf("%d%d",&m,&n);
        for(int i=0;i<m;i++)
            scanf("%s",map[i]);
        int tot=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(map[i][j]=='#'){
                    tot++;///找到一個羊群
                    dfs(i,j);
                }
            }
        }
        printf("%d\n",tot);
    }
    return 0;
}