uva 11094 Continents

用 BFS 把相鄰的土地算出來有幾個，找非國王目前位置的區域有最多相鄰土地的區

域，土地的個數即為解。所以一開始把國王目前位置用 BFS 走過，之後遇到沒有被走過的，

就用 BFS找完所有相鄰的。

注意：

1. land 有可能用 w 表示 ，因為題目沒有限定 land 和 water 是甚麼代號，所以不能把走過的地

方在地圖上標示 w。 (這題原本我是把走過的在地圖標上 w ，但是 runtime error，猜測 land 在

測資中可能有些用 w 表示)

2.右邊的邊界和左邊的邊界是互通的。



#include <stdio.h>
#include <stdlib.h>

char maps[21][21]={0},passed[21][21]={0};
int M,N;
char land;

struct point{
    int x,y;
};

int BFS(int x,int y){
    struct point queueList[441];
    struct point tmp,newLand;
    int top,head;

    top=-1; head=0;
    queueList[++top].x=x;
    queueList[top].y=y;
    passed[x][y]=1;

    while(head<=top){
        tmp=queueList[head];
        passed[tmp.x][tmp.y]=1;

        x=tmp.x; y=(tmp.y+1)%N;
        if(maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        x=tmp.x+1; y=tmp.y;
        if(x<M && maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        x=tmp.x; y=tmp.y-1;
        if(y<0) y=N-1;
        if(maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        x=tmp.x-1; y=tmp.y;
        if(x>=0 && maps[x][y]==land && passed[x][y]==0){
            newLand.x=x; newLand.y=y;
            queueList[++top]=newLand;
            passed[x][y]=1;
        }

        ++head;
    }

    return top+1;
}

int main(void){
    int maximum,landSize;
    int curM,curN;
    int i,j;


    while( scanf("%d %d",&M,&N)!=EOF ){
        for(i=0;i<M;i++){
            scanf("%s",&maps[i]);
        }
        scanf("%d %d",&curM,&curN);
        land=maps[curM][curN];

        BFS(curM,curN);

        maximum=0;
        for(i=0;i<M;i++){
            for(j=0;j<N;j++){
                if(maps[i][j]==land && passed[i][j]==0){
                    landSize = BFS(i,j);

                    if(landSize>maximum) maximum=landSize;
                }
            }
        }

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

        memset(passed,0,sizeof(passed));
    }


    return 0;
}