Mô tả vấn đề

Có một căn phòng hình chữ nhật được lát bằng các viên gạch vuông màu đen và đỏ. Bạn đứng trên một viên gạch đen và chỉ có thể di chuyển đến các viên gạch đen khác nằm liền kề (trên, dưới, trái, phải). Hãy viết chương trình để tính tổng số viên gạch đen bạn có thể đi đến.

Định dạng đầu vào

Đầu vào bao gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu bắt đầu bằng hai số nguyên W và H, tương ứng với số lượng viên gạch theo chiều ngang và chiều dọc. Tiếp theo là H dòng, mỗi dòng chứa W ký tự. Các ký tự này biểu thị màu sắc của các viên gạch như sau:

• '.' : Viên gạch đen
• '#': Viên gạch đỏ
• '@': Viên gạch đen mà bạn đang đứng. Ký tự này chỉ xuất hiện một lần trong mỗi bộ dữ liệu.

Khi đọc vào hai số 0, nghĩa là kết thúc đầu vào.

Định dạng đầu ra

Đối với mỗi bộ dữ liệu, in ra một dòng chứa số lượng viên gạch đen bạn có thể đi đến (bao gồm cả viên gạch ban đầu).

Phạm vi dữ liệu

1 ≤ W, H ≤ 20

Ví dụ

Đầu vào:

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

Đầu ra:

45
</strong>

Lời giải

Sử dụng thuật toán tìm kiếm sâu (DFS) để đếm số lượng viên gạch đen có thể đi đến. Mã nguồn C++ được cung cấp dưới đây sử dụng DFS để giải quyết vấn đề.

Mã nguồn C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 25;
char grid[N][N];
int width, height;
bool visited[N][N];

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

int dfs(int x, int y) {
    int count = 1;
    visited[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
        if (grid[nx][ny] != '.') continue;
        if (visited[nx][ny]) continue;

        count += dfs(nx, ny);
    }

    return count;
}

int main() {
    while (cin >> height >> width, width || height) {
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                cin >> grid[j][i];
            }
        }

        int startX, startY;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[j][i] == '@') {
                    startX = j;
                    startY = i;
                }
            }
        }

        memset(visited, 0, sizeof visited);
        cout << dfs(startX, startY) << endl;
    }

    return 0;
}