九章算法 | Facebook 面试题 : 岛的周长

2017-12-21

题目描述

以二维整数网格的形式给出地图，1代表陆地，0代表水。网格单元水平/垂直连接（不包含对角）。整张地图被水完全包围，并且有一个岛（即一个或多个连接的陆地单元）。岛上没有“湖泊”（里面的水没有连接到岛外的水）。一个单元格是边长为1的正方形。 网格为矩形，宽度和高度不超过100。确定岛屿的周长。

样例

输入： [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]输出：16

解答

根据观察我们可以得知，如果某个岛屿的周围有一个岛屿的话，那么它的周围有三边的海，以此类推，我们可以观察出规律... #include<iostream> #include<cstring> using namespace std;const int N = 10; int x[N+1][N+1]; int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1};int main(){int n;cin>>n;memset(x,0,sizeof(x));int cnt=0;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){cin>>x[i][j];}}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (x[i][j]){for (int k=0;k<4;k++){if (!x[i+dx[k]][j+dy[k]]) cnt++;} }}}cout<<cnt<<endl;return 0; } 可能我们用if判断也可以得出结果，但是这样的代码一定没有这样优美...

总结

以上是生活随笔为你收集整理的九章算法 | Facebook 面试题 : 岛的周长的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。