挑戰程式設計競賽練習題解析（深度優先搜尋DFS）

Lake Counting(POJ No.2386)

poj1979-Red and Black

#include<iostream>
using namespace std;
int ans=0,N,M;
char mess[20][21];
//因為隻能移動四個方向是以用數組來存
int dx[]={-1,0,0,1};
int dy[]={0,1,-1,0}; 
void dfs(int x,int y)
{
    mess[x][y]='#';
    ++ans;
    for(int i=0;i<4;++i)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=0&&nx<M&&ny>=0&&ny<N&&mess[nx][ny]=='.')
            dfs(nx,ny);
    }
    return ;
}
int main()
{
    while(cin>>N>>M&&N!=0)
    {int x,y;
    for(int i=0;i<M;++i)
      for(int j=0;j<N;++j)
      {
          cin>>mess[i][j];
          if(mess[i][j]=='@')
            { x=i; y=j; }
      }
    dfs(x,y);
    cout<<ans<<endl;
    ans=0;    //因為是多組輸入，記得将ans歸零
    }
    return 0;
}
           

AOJ 0118:Property Distribution

題目大緻意思為分為三種地，分别用@#*代替，符号相同的連續的為一塊地，請你算出一共有多少塊地。

#include<iostream>
#define M 100
using namespace std;
char field[M][M];
int dx[]={-1,0,0,1};
int dy[]={0,1,-1,0};
int H,W;
void dfs(int x,int y,char ch)  //用參數ch保證判斷的是同一符号
{
    field[x][y]='$';   //将搜尋過的替換成其他的符号
    for(int i=0;i<4;++i)
    {
        int nx=x+dx[i],ny=y+dy[i];
        if(nx>=0&&nx<H&&ny>=0&&ny<W&&field[nx][ny]==ch)
          dfs(nx,ny,ch);
    }
}
void solve()
{
    int res=0;
    for(int i=0;i<H;++i)
       for(int j=0;j<W;++j)
        if(field[i][j]!='$')
           {
              dfs(i,j,field[i][j]);
              ++res;
           }
    cout<<res<<endl;
}
int main()
{
    while(cin>>H>>W&&H!=0)
    {   for(int i=0;i<H;++i)
          for(int j=0;j<W;++j)
             cin>>field[i][j];
        solve();
    }
    return 0;
}
           

AOJ 0033:Ball

有一說一感覺這題不是dfs，就是看有沒有兩組從小到大排列的數，直接輸入再用兩個數存就行了。

#include<iostream>
using namespace std;
int main()
{
    int N;
    cin>>N;
    while(N--)
    {
        int a=0,b=0;
        int temp;
        bool f=true;
        for(int i=0;i<10;++i)
        {
            cin>>temp;
            if(temp>a) a=temp;
            else if(temp>b) b=temp;
            else f=false;
        }
        if(f) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
           

POJ 3009：Curling 2.0