本篇同步發布於Blog: [解題] LeetCode - 200 Number of Islands

平台：

LeetCode

題號：

200 - Number of Islands

題目連結：

https://leetcode.com/problems/number-of-islands/

題目說明：

        輸入2維字元陣列，也代表一張地圖，只有1和0組成，1代表土地、0代表水域。只要地圖上下左右是1相鄰，能組成一座島嶼。求這張地圖有多少座島嶼。

比如範例輸入

grid = [

  ["1","1","0","0","0"],

  ["1","1","0","0","0"],

  ["0","0","1","0","0"],

  ["0","0","0","1","1"]

]

有左上角4個1、中間1個1、右下角2個1，共3座島嶼。

解題方法：

   　經典的DFS問題，開一個Visit紀錄已經拜訪過的區域，從左上開始搜尋，遇到尚未拜訪的1字元就區域搜尋，累加每次搜尋的次數為答案。

難度為Medium  (個人覺得Easy)

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
using namespace std;


class Solution {
private:
    const int dx[4] = {1,0,-1,0};
    const int dy[4] = {0,1,0,-1};
    int row, col;
    bool** visit;
    void dfs(int r, int c, vector<vector<char>>& grid){
        visit[r][c] = true;
        for(int d = 0 ; d < 4;++d){
            int ny = r + dy[d];
            int nx = c + dx[d];
            if(ny >= 0 && ny < row && nx >= 0 && nx < col && grid[ny][nx] == '1' && !visit[ny][nx]){
                dfs(ny, nx, grid);
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size() == 0){
            return 0;
        }
        
        int ans = 0;
        row = grid.size();
        col = grid[0].size();
        
        visit = new bool*[row];
        for(int i = 0; i < row; ++i){
            visit[i] = new bool[col];
        }
            
        
        for(int i = 0 ; i < row;++i){
            for(int j = 0 ; j < col;++j){
                visit[i][j] = false;
            }
        }
        
        for(int i = 0 ; i < row;++i){
            for(int j = 0 ; j < col;++j){
                if(grid[i][j] == '1' && !visit[i][j]){
                    dfs(i, j, grid);
                    ans++;
                }
            }
        }
        
        return ans;
    }
};

int main() {
	
	vector<vector<char>> grid;
	vector<char> row1{'1', '1', '0', '0', '0'};
	vector<char> row2{'1', '1', '0', '0', '0'};
	vector<char> row3{'0', '0', '1', '0', '0'};
	vector<char> row4{'0', '0', '0', '1', '1'};
	grid.push_back(row1);
	grid.push_back(row2);
	grid.push_back(row3);
	grid.push_back(row4);
	Solution sol;
	cout << sol.numIslands(grid) << endl;
	return 0;
}

using System;

namespace LeetCode200
{
    public class Solution
    {

        private readonly static int[] dx = new int[] { 1, 0, -1, 0 };
        private readonly static int[] dy = new int[] { 0, 1, 0, -1 };
        private int row, col;
        private bool[][] visit;

        private void dfs(int r, int c, char[][] grid)
        {
            visit[r][c] = true;
            for (int d = 0; d < 4; ++d)
            {
                int ny = r + dy[d];
                int nx = c + dx[d];
                if (ny >= 0 && ny < row && nx >= 0 && nx < col && grid[ny][nx] == '1' && !visit[ny][nx])
                {
                    dfs(ny, nx, grid);
                }
            }
        }
        public int NumIslands(char[][] grid)
        {
            if (grid.Length == 0)
            {
                return 0;
            }

            int ans = 0;
            row = grid.Length;
            col = grid[0].Length;

            visit = new bool[row][];
            for (int i = 0; i < row; ++i)
            {
                visit[i] = new bool[col];
            }


            for (int i = 0; i < row; ++i)
            {
                for (int j = 0; j < col; ++j)
                {
                    visit[i][j] = false;
                }
            }

            for (int i = 0; i < row; ++i)
            {
                for (int j = 0; j < col; ++j)
                {
                    if (grid[i][j] == '1' && !visit[i][j])
                    {
                        dfs(i, j, grid);
                        ans++;
                    }
                }
            }

            return ans;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            char[][] grid = new char[4][];
            grid[0] = new char[5]{'1', '1', '0', '0', '0'};
            grid[1] = new char[5]{'1', '1', '0', '0', '0'};
            grid[2] = new char[5]{'0', '0', '1', '0', '0'};
            grid[3] = new char[5]{'0', '0', '0', '1', '1'};
            Solution sol = new Solution();
            Console.WriteLine(sol.NumIslands(grid));
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/200-299/200.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/200-299/200.cs