#include <vector> // both m*n 
using namespace std;
class Solution {
public:
    int numIslands(vector<vector<char>>& g){
        int m = g.size();
        if (m == 0) return 0;
        int n = g[0].size();
        if (n == 0) return 0;
        int ans = 0;
        static const int dx[4] = {1, -1, 0, 0};
        static const int dy[4] = {0, 0, 1, -1};
        vector<int> q;
        q.reserve(m * n);
        for (int r = 0 ; r < m ; ++r) for (int c = 0 ; c < n ; ++c){
            if (g[r][c] != '1') continue;
            ++ans;
            g[r][c] = '0';
            q.clear();
            q.push_back(r * n + c);
            for (int head = 0 ; head < (int)q.size() ; ++head){
                int id = q[head];
                int x = id / n, y = id % n;
                for (int k = 0 ; k < 4 ; ++k){
                    int nx = x + dx[k], ny = y + dy[k];
                    if ((unsigned)nx >= (unsigned)m || (unsigned)ny >= (unsigned)n) continue;
                    if (g[nx][ny] == '1'){
                        g[nx][ny] = '0';
                        q.push_back(nx * n + ny);
                    }
                }
            }
        }
        return ans;
    }
};