3965 - D.岛屿面积有多大
若海域由一个主岛和一些附属岛屿组成，海域可由一个n×n的方阵表示，矩阵中的数字表示相应主岛或岛屿的海拔：数字1～9表示陆地，数字0表示海洋。
现在A君打算在某个岛屿或主岛上探险，他的飞机将会降落在海域坐标为(x, y)的陆地上，请你计算A君降落点所在岛屿或主岛的面积有多大，此处将面积定义为满足4连通的格子有多少个，4连通即为将与A君降落点上下左右相邻接的陆地均视为同一岛屿或主岛。
Input
输入一行包含3个整型数据，第一个用于表示海域的总面积，即n行n列（1<=n<=30）的方形区域；后两个用于表示A君的降落点坐标x和y（1<=x, y <=n）。
Output
A君降落点所在岛屿或主岛的面积。
Examples
Input
3 1 1 1 1 0 2 1 0 0 0 0 5 2 4 0 1 1 5 0 2 2 3 1 1 2 0 0 2 0 0 1 3 1 0 1 0 1 0 0 10 6 8 1 2 1 0 0 0 0 0 2 3 3 0 2 0 1 2 1 0 1 2 4 0 1 0 1 2 3 2 0 1 3 2 0 0 0 1 2 4 0 0 0 0 0 0 0 0 1 5 3 0 0 1 2 1 0 1 5 4 3 0 0 1 2 3 1 3 6 2 1 0 0 0 3 4 8 9 7 5 0 0 0 0 0 3 7 8 6 0 1 2 0 0 0 0 0 0 0 0 1 0
Output
4 14 38
Solution C
#include<stdio.h> #include<string.h> struct Node { int X, Y; }; int main( int argc, char **argv ) { int N, StartX, StartY; while( scanf( "%d%d%d", &N, &StartX, &StartY ) != EOF ) { struct Node Queue[1000]; int Head, Tail; int Map[31][31], Book[31][31] = { 0 }; int i, j, k, Sum, TmpX, TmpY; int Next[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; for( i = 1; i <= N; ++i ) for( j = 1; j <= N; ++j ) scanf( "%d", &Map[i][j]); Head = 0, Tail =0; Queue[Tail].X = StartX, Queue[Tail].Y = StartY; Tail++; Book[StartX][StartY] = 1; Sum = 1; while( Head < Tail ) { for( k = 0; k < 4; ++k ) { TmpX = Queue[Head].X + Next[k][0], TmpY = Queue[Head].Y + Next[k][1]; if( TmpX < 1 || TmpX > N || TmpY < 1 || TmpY > N ) continue; if( Map[TmpX][TmpY] > 0 && Book[TmpX][TmpY] == 0 ) { Sum++; Book[TmpX][TmpY] = 1; Queue[Tail].X = TmpX, Queue[Tail].Y = TmpY; Tail++; } } Head++; } printf( "%d\n", Sum ); } return 0; }
Solution C++
#include <stdio.h> #include <iostream> using namespace std; struct note { int x; int y; }; int main() { // 满足4连通的海域点 int next[4][2] = { { 0, 1 }, // 右 { 1, 0 }, // 下 { 0, -1 }, // 左 { -1, 0 } // 上 }; int n, startx, starty; // 海域尺寸n以及降落点的坐标(startx,starty) while (cin >> n >> startx >> starty) { struct note que[901]; int head, tail; int a[31][31]; int book[31][31] = { 0 }; int i, j, k, sum, max = 0, targetx, targety; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) cin >> a[i][j]; head = 1; tail = 1; que[tail].x = startx; // 往队列插入降落的起始坐标 que[tail].y = starty; tail++; book[startx][starty] = 1; // 陆地点标记 sum = 1; // 陆地面积 while (head<tail) { for (k = 0; k <= 3; k++) // 逐一判断满足4连通的海域点：是否为陆地或者曾经遍历 { targetx = que[head].x + next[k][0]; targety = que[head].y + next[k][1]; if (targetx<1 || targetx>n || targety<1 || targety>n) continue; if (a[targetx][targety]>0 && book[targetx][targety] == 0) { sum++; book[targetx][targety] = 1; que[tail].x = targetx; que[tail].y = targety; tail++; } } head++; } cout << sum << endl; } return 0; }