DFSは連通する領域全体を遍歴する

DFSは検索中に大きなものを検索することができます.
接続された領域.
テーマ:http://acm.swust.edu.cn/oj/problem/1/


View Code

#include<iostream>
#include<string.h>
using namespace std;
int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int used[1005][85];
char map[1005][85];
int W, H, i, j, count, Max, tx, ty;
void dfs(int i, int j)
{
    int k;
    count++;
    used[i][j] = 1;
    for(k=0; k<4; k++)
    {
        tx = i + direction[k][0];  ty = j + direction[k][1];
        if(tx>=0 && tx<H && ty>=0 && ty<W && used[tx][ty]==0 && map[tx][ty]=='*')
            dfs(tx, ty);
    }
}
int main()
{    
    while(cin>>W>>H)
    {
        memset(used, 0, sizeof(used));
        Max = 0;
        for(i=0; i<H; i++)
            for(j=0; j<W; j++)
                cin>>map[i][j];
        for(i=0; i<H; i++)
            for(j=0; j<W; j++)
            {
                if(map[i][j]=='*' && used[i][j]==0)
                {
                    count = 0;
                    dfs(i, j);
                    if(count>Max)
                        Max = count;
                }
            }
        cout<<Max<<endl;
    }
    return 0;
}