一、原題

對(duì)于一個(gè)01矩陣A，求其中有多少片連成一片的1。每個(gè)1可以和上下左右的1相連。

請(qǐng)為下面的Solution類實(shí)現(xiàn)解決這一問題的函數(shù)countConnectedOnes，函數(shù)參數(shù)A為給出的01矩陣，A的行數(shù)和列數(shù)均不大于1000。函數(shù)的返回值是問題的答案。

例1：
A=
100
010
001
答案為3.

例2：
A=
1101
0101
1110
答案為2.

二、思路

該題明顯就是一個(gè)圖的廣度優(yōu)先遍歷的題目，從圖中一個(gè)1開始作為起點(diǎn)，使用廣度優(yōu)先遍歷，遍歷的步驟如下：

1. 將起點(diǎn)S（節(jié)點(diǎn)值為1）存入到一個(gè)隊(duì)列中；
2. 從隊(duì)列中取出一個(gè)節(jié)點(diǎn)N（第一次執(zhí)行時(shí)候該節(jié)點(diǎn)便是起點(diǎn)S），將該節(jié)點(diǎn)N周邊（左右上下四個(gè)方位）為1的節(jié)點(diǎn)也存儲(chǔ)到隊(duì)列中；
3. 重復(fù)步驟2直至隊(duì)列為空；
4. 此時(shí)遍歷完一個(gè)包含S的區(qū)域，結(jié)果值加1；
5. 重復(fù)步驟1直至遍歷所有起點(diǎn)；

三、時(shí)間優(yōu)化

大體思路如上，但還需注意一些細(xì)節(jié)，這些細(xì)節(jié)能夠節(jié)省執(zhí)行的時(shí)間：

• 對(duì)于每一個(gè)起點(diǎn)S，可以將該節(jié)點(diǎn)置為0，避免后面在廣度優(yōu)先遍歷中重復(fù)將該起點(diǎn)S加入到隊(duì)列中；
• 對(duì)于一個(gè)節(jié)點(diǎn)N的廣度遍歷，當(dāng)掃描到下一個(gè)節(jié)點(diǎn)M為1時(shí)，立即將節(jié)點(diǎn)M置為0，能夠防止別其他節(jié)點(diǎn)N'重復(fù)將M加入到隊(duì)列中（這個(gè)是我前幾次超時(shí)的主要原因）；

通過以上兩點(diǎn)，能夠保證矩陣每一個(gè)值為1節(jié)點(diǎn)只被放入到隊(duì)列中一次，也就是保證每一個(gè)1只被檢測一遍。

四、代碼

struct Node {
    int x;
    int y;

    Node(int r, int c) {
        x = r;
        y = c;
    }
};

int countConnectedOnes(vector<vector<char>> &A) {
    if (A.empty() || A[0].empty()) {
        return 0;
    }

    set<Node> locOfOne;
    int row = A.size();
    int col = A[0].size();

    queue<Node> que;
    int ans = 0;

    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            if (A[i][j] == '0') {
                continue;
            }

            A[i][j] == '0';          
            Node n(i, j);
            while (!que.empty()) {
                que.pop();
            }
            que.push(n); // 步驟1

            while (!que.empty()) {
                Node tmp = que.front(); // 步驟2
                que.pop();

                // MOVE LEFT
                if (tmp.y - 1 >= 0 && A[tmp.x][tmp.y - 1] == '1') {
                    A[tmp.x][tmp.y - 1] = '0'; // 在這里設(shè)置為0能夠防止一個(gè)節(jié)點(diǎn)被放入到隊(duì)列兩次，下同
                    Node left(tmp.x, tmp.y - 1);
                    que.push(left);
                }

                // MOVE RIGHT
                if (tmp.y + 1 < col && A[tmp.x][tmp.y + 1] == '1') {
                    A[tmp.x][tmp.y + 1] = '0';
                    Node right(tmp.x, tmp.y + 1);
                    que.push(right);
                }

                // MOVE UP
                if (tmp.x - 1 >= 0 && A[tmp.x - 1][tmp.y] == '1') {
                    A[tmp.x - 1][tmp.y] = '0';
                    Node up(tmp.x - 1, tmp.y);
                    que.push(up);
                }

                // MOVE DOWN
                if (tmp.x + 1 < row && A[tmp.x + 1][tmp.y] == '1') {
                    A[tmp.x + 1][tmp.y] = '0';
                    Node down(tmp.x + 1, tmp.y);
                    que.push(down);
                }
            } // 步驟3
            ans++; // 步驟4
        }
    } // 步驟5
    return ans;
}