天生勇气 2018-03-01
有一块矩形的海域,其中有陆地也有海洋,这块海域是CSUFT_ACM集训队的训练基地,这一天,昌神说要集训队的队员不能总是训练,于是昌神提出了中南林ACM集训队第一场环陆马拉松比赛,顾名思义就是围绕着陆地的边缘跑步。现在昌神给你出了个问题:这个比赛最多需要跑多少距离。
注意,这块海域上可能有多块陆地,比赛的场地可能设在任何一块陆地上。
输入
多组输入,每组输入第一行给出两个数字R,C(1 ≤ R, C ≤ 50)。表示这组输入的01矩阵的行数和列数,接下来R行每行输入C个数字(0表示海水,1表示陆地),上下左右相连的陆地算作一块整的陆地。每个0或者1表示一个边长为1正方形。输入保证至少有一块陆地。
输出
输出陆地周长的最大值。里面的边长也要算在内,例如上图中有四块陆地,最长周长是12 + 4=16。第二长的周长是8,最小的周长是4。
样例输入
1 1
1
6 5
01110
01010
01110
00000
01010
10011
样例输出
4
16
#include <iostream> using namespace std; #include <algorithm> #include <cstdio> int map[60][60]; int Max; int s,n,m; int dir[5][2]={0,1,0,-1,1,0,-1,0}; void dfs(int x,int y) { int i,j,t=0; int xx,yy; for(i=0;i<4;i++){ xx=x+dir[i][0]; yy=y+dir[i][1]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&(map[xx][yy]==1||map[xx][yy]==2)) t++; } s=s+4-t; if(s>Max) Max=s; map[x][y]=2; for(i=0;i<4;i++){ xx=x+dir[i][0]; yy=y+dir[i][1]; if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[xx][yy]==1){ map[xx][yy]=2; dfs(xx,yy); } } } int main() { int i,j,k; while(cin>>n>>m){ Max=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++) scanf("%1d",&map[i][j]); } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ s=0; if(map[i][j]==1){ dfs(i,j); } } } cout<<Max<<endl; } }
解题思路:
找到一共有几块相连的陆地, 每一个陆地上小正方形的 周长 = 4- 周围是陆地的数量 。