<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>
###### tags: `Meowmeow Online Judge`

# Counting Rooms
## Description

You are given a map of a building, and your task is to count the number of its rooms. The size of the map is $n×m$ squares, and each square is either floor or wall. You can walk left, right, up, and down through the floor squares.

## Input
The first line has two integers nn and mm: the height and width of the map.

Then there are nn lines of mm characters describing the map. Each character is either . (floor) or # (wall).

1 $10001≤n,m≤1000$

## Output
Print one integer: the number of rooms.

## 解題思路
從(0,0)到(n - 1, m - 1)，遇到floor做BFS把同一個room的floor都填成wall，並把room數+1
### 時間複雜度
$O(n*m)$

## Code

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <string>

int main() {
    int height, width;
    int rooms = 0;

    std::cin >> height >> width;

    std::vector<std::string> building(height);

    for (auto &it : building) std::cin >> it;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (building[i][j] == '.') {
                rooms++;
                std::deque< std::pair<int, int> > dq;
                building[i][j] = '#';
                dq.emplace_back(i, j);
                while (!dq.empty()) {
                    auto &f = dq.front();
                    // std::cout << f.first << ',' << f.second << std::endl;
                    if (f.first - 1 >= 0 && building[f.first - 1][f.second] == '.') {
                        building[f.first - 1][f.second] = '#';
                        dq.emplace_back(f.first - 1, f.second);
                    }
                    if (f.first + 1 < height && building[f.first + 1][f.second] == '.') {
                        building[f.first + 1][f.second] = '#';
                        dq.emplace_back(f.first + 1, f.second);
                    }
                    if (f.second - 1 >= 0 && building[f.first][f.second - 1] == '.') {
                        building[f.first][f.second - 1] = '#';
                        dq.emplace_back(f.first, f.second - 1);
                    }
                    if (f.second + 1 < width && building[f.first][f.second + 1] == '.') {
                        building[f.first][f.second + 1] = '#';
                        dq.emplace_back(f.first, f.second + 1);
                    }
                    dq.pop_front();
                }
            }
        }
    }
    std::cout << rooms << std::endl;
}