題目連接

題目描述

神秘的海洋，驚險(xiǎn)的探險(xiǎn)之路，打撈海底寶藏，激烈的海戰(zhàn)，海盜劫富等等。加勒比海盜，你知道吧？杰克船長(zhǎng)駕駛著自己的的戰(zhàn)船黑珍珠1號(hào)要征服各個(gè)海島的海盜，最后成為海盜王。??這是一個(gè)由海洋、島嶼和海盜組成的危險(xiǎn)世界。面對(duì)危險(xiǎn)重重的海洋與詭譎的對(duì)手，如何憑借智慧與運(yùn)氣，建立起一個(gè)強(qiáng)大的海盜帝國(guó)。

杰克船長(zhǎng)手頭有一張整個(gè)海域的海圖，上面密密麻麻分布著各個(gè)海嶼的位置及面積。他想盡快知道整個(gè)海域共有多少島嶼以及最大島嶼的面積。

輸入

第1行:M N T，表示海域的長(zhǎng)，寬及一個(gè)單位表示的面積大小
接下來(lái)有M行 ,每行有N個(gè)01組成的序列以及其中穿插一些空格。0表示海水，1表示陸地，其中的空格沒(méi)用，可以忽略掉。

輸出

輸出一行，有2個(gè)整數(shù)，一個(gè)空格間隔，表示整個(gè)海域的島嶼數(shù)，以及最大島嶼的面積

樣例輸入

8 16 99 00000000 00000000 0000110011000000 0001111000111000 0000000 00 0000000 00111 111000001 10 001110000 0000000 0100001111 111100 0000000000000000

樣例輸出

5 990

提示

①若一個(gè)陸地八個(gè)方向之一（上、下、左、右、左上、右上、左下、右下）的位置也是陸地，則視為同一個(gè)島嶼。
② 假設(shè)第一行，最后一行，第一列，最后一列全為0.

③ 1<M, N≤500 1<T≤100000

簡(jiǎn)單搜索題，深搜一次就出結(jié)果了，定義一個(gè)標(biāo)記數(shù)組記錄走過(guò)的位置，如下代碼：

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring>using namespace std;char map[505][505]; bool vis[505][505]; int Max;void dfs(int x, int y){if(map[x][y]=='0' || vis[x][y]==true )return ;++Max;vis[x][y]=true;dfs(x+1,y);dfs(x+1,y+1);dfs(x,y+1);dfs(x-1,y+1); dfs(x-1,y);dfs(x-1,y-1);dfs(x,y-1);dfs(x+1,y-1); }int main(){int m,n,t;while(scanf("%d %d %d",&m,&n,&t)!=EOF){memset(map,0,sizeof(map));memset(vis,false,sizeof(vis));for(int i=0; i<m; ++i){getchar();for(int j=0; j<n; ++j){char c=getchar();if(c==' ')--j;elsemap[i][j]=c;}}int count=0,max=0;for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){if(map[i][j]=='1' && !vis[i][j] ){Max=0;count++;dfs(i,j);//vis[i][j]=false;if(max<Max)max=Max;} }}printf("%d %d\n",count,max*t);} return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ_5739最大岛屿(河南省第八届acm程序设计大赛)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。