3965 - D.岛屿面积有多大
时间限制 : 1 秒
内存限制 : 128 MB
若海域由一个主岛和一些附属岛屿组成，海域可由一个n×n的方阵表示，矩阵中的数字表示相应主岛或岛屿的海拔：数字1～9表示陆地，数字0表示海洋。
现在A君打算在某个岛屿或主岛上探险，他的飞机将会降落在海域坐标为(x, y)的陆地上，请你计算A君降落点所在岛屿或主岛的面积有多大，此处将面积定义为满足4连通的格子有多少个，4连通即为将与A君降落点上下左右相邻接的陆地均视为同一岛屿或主岛。
题目输入
输入一行包含3个整型数据，第一个用于表示海域的总面积，即n行n列（1<=n<=30）的方形区域；后两个用于表示A君的降落点坐标x和y（1<=x, y <=n）。
题目输出
A君降落点所在岛屿或主岛的面积。
输入/输出样例
输入格式
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
输出格式
4 14 38
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; }
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; }
Java解答
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner in = new Scanner(System.in); while(in.hasNext()){ int n =in.nextInt(); int a =in.nextInt(); int b =in.nextInt(); int[][] map = new int[n][n]; boolean[][] visited = new boolean[n][n]; for(int i=0;i<visited.length;i++){ for(int k=0;k<visited[0].length;k++) visited[i][k] =false; } for(int i=0;i<map.length;i++){ for(int k=0;k<map[0].length;k++) map[i][k] =in.nextInt(); } int count =find(map,visited,a-1,b-1); System.out.println(count); } } private static int find(int[][] map, boolean[][] visited, int i, int j) { // TODO Auto-generated method stub if(i<0||i>=map.length||j<0||j>=map[0].length||visited[i][j]==true||map[i][j]==0) return 0; else{ visited[i][j] = true; return 1+find(map,visited,i-1,j)+ find(map,visited,i+1,j)+ find(map,visited,i,j+1)+ find(map,visited,i,j-1); } } }