YTU OJ 3389: 小岛面积-期末考试试题

3389: 小岛面积-期末考试试题

 

题目描述

  上面矩阵的中的1代表海岸线，0代表小岛。求小岛面积（即被1中包围的0的个数）的最大值。 

 

输入

第一行输入一个整数N(1<=N<=100)，表示输入方阵的维数 

输入一个N维方阵 

 

 

输出

小岛面积

 

 

提示

DFS求最大面积

 

来源/分类

BUAA2012-2 

 

 

#include <iostream> #include <cstdio> using namespace std; int n; int maps[99][99]; int dx[4] = {0,-1,0,1}; int dy[4] = {-1,0,1,0}; int ans = 0;//记录岛屿个数 void dfs(int x,int y) { if(x<0||y<0||x>=n||y>=n){ return ; } if(maps[x][y]==1||maps[x][y]==2){ return ; } maps[x][y] = 2; ans++; for(int i=0;i<4;i++){ int nx = x + dx[i]; int ny = y + dy[i]; dfs(nx,ny); } return ; } int main() { cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>maps[i][j]; } } int maxn = -1; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(maps[i][j]==0){ ans = 0; //每次记录 dfs(i,j); } else{ maxn = max(maxn,ans); } } } cout<<maxn<<endl; return 0; }