[UVA] 11094 - Continents
Problem
A
Continents
Time Limit:
1 Second
Mijid the Great is the king of Dodars territory. He likes to travel between the cities in his territory and actually, you can never see him in the same city as where he was the day before. Therefore, he captured all territories of his continent! In spite of this fact, he has seen all cities of his territory so far and wants to capture another continent in order to have some choices to travel into new cities. Now, having the world map, he needs your help to find the biggest continent except the one in which he resides.
Maps are given as M x N tables, filled with at most two different letters denoting land and water regions. A continent is a set of connected land regions which is completely surrounded by water regions or the end of map. Two regions are assumed to be connected if they have an edge in common. The coordinates of top left region is (0,0) and bottom right region (M-1,N-1). Region with coordinates (x,N-1) should be assumed to have a common edge with region (x,0) for every x between 0 and M-1 (inclusive).
Input
There will be several test cases. Each test case contains two integers M<=20 and N<=20 in the first line denoting the number of rows and columns in the map respectively. Next, there will be M lines of exactly N characters representing the map. Finally in the last line there would be two integers 0<=X<M and 0<=Y<N , the coordinates of the region in which Mijid the Great currently stays. There will one blank line after each test case.
Output
For each test case, output a line containing an integer that is the number of regions in the biggest continent that Mijid the Great can capture.
Sample Input Output for Sample Input
5 5
wwwww
wwllw
wwwww
wllww
wwwww
1 3
|
2
|
但 x 卻不是, 陸地相鄰的定義是四周四塊而已, 求除了國王所在位置的最大陸地
#include <stdio.h>
#include <string.h>
int n, m, i, j, ans, sum;
char map[21][21], used[21][21], land;
void dfs(int x, int y) {
if(y < 0) y = m-1;
if(y >= m) y = 0;
if(x < 0 || x >= n)
return ;
if(used[x][y] != 0 || map[x][y] != land)
return ;
used[x][y] = 1;
sum++;
dfs(x+1, y);
dfs(x, y+1);
dfs(x-1, y);
dfs(x, y-1);
}
int main() {
while(scanf("%d %d", &n, &m) == 2) {
memset(used, 0, sizeof(used));
for(i = 0; i < n; i++)
scanf("%s", map[i]);
scanf("%d %d", &i, &j);
land = map[i][j];
dfs(i, j);
ans = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
sum = 0;
dfs(i, j);
if(sum > ans)
ans = sum;
}
}
printf("%d\n", ans);
}
return 0;
}