dfs連通塊2

hdu1312Red and Black

題目連結http://acm.hdu.edu.cn/showproblem.php?pid=1312；

我隻能說，我一定要好好學會搜尋，

這其實是一道我們學校省賽隊伍選拔的搜尋水題，

隊伍裡面本來是我負責搜尋這一子產品，但因為自己沒有放在心上，是以沒有去學習，這一子產品；在比賽的時候發費了好多時間還是沒做出來；

但是的困惑就是要怎麼達到搜尋的目的呢？怎麼向四周搜尋，然後遇到不成立之後又退出傳回到原來的地方繼續另外一邊的搜尋呢？

後來看了解題報告才知道是用遞歸函數調用來實作的，再已仔細想，确實哈；

用遞歸哈？函數調用，當初了解漢若塔就是這樣的，用樹去了解，一下就明朗多了；

int sum,a,b,map[22][22];
int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//四周 
void dfs(int si, int sj)
{
    int x,y,i;
    for(i =0;i < 4; i++){
        x = fx[i][0]+si;
        y = fx[i][1]+sj;
        if(x>=0&&x<b&&y>=0&&y<a&&map[x][y]=='.'){
            sum++;
            map[x][y]='#';
            dfs(x,y);
            //printf("%d\n",i);//特别注意i不能宏觀定義 
        }
    }
}
           

看了dfs部分的代碼是不是十分熟悉哈；其實這比漢若塔的函數調用要簡單一些，隻是一個函數的自我調用，而漢若塔涉及到了多個函數；隻是這裡多了一個循環，最後傳回到原處之後要進行循環，再次進行判斷調用；

看題目源代碼；其實也不是思路出來了，然後ac其實也不是這麼容易的；

1；往四周搜尋使用一個二維數組與一個循環來完成的；

2；搜尋完這個點之後要把它清為’#’；

3；輸入的時候要注意getchar的搭配；

#include<stdio.h>
int sum,a,b,map[][];
int fx[][]={{,},{-,},{,},{,-}};//四周 
void dfs(int si, int sj)
{
    int x,y,i;
    for(i =;i < ; i++){
        x = fx[i][]+si;
        y = fx[i][]+sj;
        if(x>=&&x<b&&y>=&&y<a&&map[x][y]=='.'){
            sum++;
            map[x][y]='#';
            dfs(x,y);
            //printf("%d\n",i);//特别注意i不能宏觀定義 
        }
    }
}
int main() 
{
    int sti,stj,j,i;
    while(scanf("%d %d",&a,&b) != EOF){
        getchar();
        if(a==&&b==)
            break;
        for(i = ; i < b; i++){//ab要搞清 
            for(j = ; j < a; j++){
                scanf("%c",&map[i][j]);
                if(map[i][j]=='@'){
                    sti=i;
                    stj=j;
                }
            }
            getchar();
        }
        sum=;
        map[sti][stj]='#';
        dfs(sti,stj);
        printf("%d\n",sum);
    }
}