URAL 1250 Sea Burial 简单Floodfill

问这个人掉落的海域包含几个岛屿。

八方向相连为同一片海域，四方向相连为同一个岛屿。与边界相连的岛屿不算。

方法：在给定地图外面填充一圈"."，从这个人掉落的地方开始进行floodfill，标出他所在的海域。

然后再从(0, 0)点进行一次floodfill，把之前标记的海域之外的东西全部清掉。

最后统计岛屿个数即可。

注意：坐标是反着的

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <algorithm>

using namespace std;

const int MAXN = ;

const int dx[] = { -, , , , -, -, , , - };

const int dy[] = { , -, , , -, , , -, - };

struct Point

{

    int x, y;

    Point( int x = , int y =  ): x(x), y(y) { }

};

Point Q[MAXN * MAXN * ];

char G[MAXN][MAXN];

bool vis[MAXN][MAXN];

int R, C, X, Y;

bool check( int x, int y, bool wh )

{

    if ( wh ) return x >  && x <= R && y >  && y <= C;

    else return x >=  && x <= R +  && y >=  && y <= C + ;

}

void FloodFill( Point st, char ch1, char ch2, char ch3, int dir )

{

    int front = , rear = ;

    bool wh = false;

    if ( dir ==  ) wh = true;

    Q[rear++] = st;

    while ( front < rear )

    {

        Point p = Q[front];

        G[ p.x ][ p.y ] = ch3;

        vis[ p.x ][ p.y ] = true;

        //printf( "%d %d\n", p.x, p.y );

        for ( int i = ; i < dir; ++i )

        {

            int xx = p.x + dx[i];

            int yy = p.y + dy[i];

            //printf( "vis[%d][%d] = %d\n", xx, yy, vis[xx][yy] );

            if ( check( xx, yy, wh ) && !vis[xx][yy] && ( G[xx][yy] == ch1 || G[xx][yy] == ch2 ) )

            {

                vis[xx][yy] = true;

                Q[rear++] = Point( xx, yy );

            }

        }

        ++front;

    }

    return;

}

int main()

{

    //freopen("s.txt", "w", stdout );

    while ( ~scanf( "%d%d%d%d", &C, &R, &Y, &X ) )

    {

        memset( G, '.', sizeof(G) );

        G[][ C +  ] = '\0';

        for ( int i = ; i <= R; ++i )

        {

            scanf( "%s", &G[i][] );

            G[i][ C +  ] = '\0';

        }

        memset( vis, false, sizeof(vis) );

        FloodFill( Point( X, Y ), '.', '.', '*',  );

        memset( vis, false, sizeof(vis) );

        FloodFill( Point( ,  ),   '.', '#', ' ',  );

        memset( vis, false, sizeof(vis) );

        int ans = ;

        for ( int i = ; i <= R; ++i )

        for ( int j = ; j <= C; ++j )

        if ( G[i][j] == '#' )

        {

            ++ans;

            FloodFill( Point( i, j ), '#', '#', '$',  );

        }

        printf( "%d\n", ans );

    }

    return ;

}