leetcode:106. 島嶼的周長

題目

題目描述

給定一個由 1（陸地）和 0（水）組成的矩陣，島嶼是被水包圍，并且通過水平方向或垂直方向上相鄰的陸地連接而成的。

你可以假設矩陣外均被水包圍。在矩陣中恰好擁有一個島嶼，假設組成島嶼的陸地邊長都為 1，請計算島嶼的周長。島嶼內部沒有水域。

輸入描述

第一行包含兩個整數 N, M，表示矩陣的行數和列數。之后 N 行，每行包含 M 個數字，數字為 1 或者 0，表示島嶼的單元格。

輸出描述

輸出一個整數，表示島嶼的周長。

思路

求周長很容易看出來，對于每個小方格而言，他的四周如果是0或者超出邊界說明這里有一條邊。

/*
計算島嶼的周長
*/
#include <bits/stdc++.h>
using namespace std;// 對于一個陸地1而言，它的四周，只要是0或者超出邊界，那就是周長的一部分int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};int main()
{int n, m;cin >> n >> m;int perimeter = 0;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> grid[i][j];}}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (grid[i][j] == 1){for (int k = 0; k < 4; k++){int nexti = i + dir[k][0];int nextj = j + dir[k][1];if (grid[nexti][nextj] == 0 || nexti < 0 || nexti >= n || nextj < 0 || nextj >= m)perimeter++;}}}}cout << perimeter << endl;return 0;
}

總結

沒用到dfs

參考資料

?代碼隨想錄