Tìm tâm của hình vuông đen bên trong ma trận bằng C++

Mô tả bài toán

Cho ma trận n x m, các ô là 'W' (trắng) hoặc 'B' (đen). Có một hình vuông có cạnh lẻ được tô đen bên trong. Cần tìm tọa độ tâm của hình vuông đó (chỉ số cột, chỉ số hàng).

Ví dụ

Ma trận 5x6:

Kết quả: (3, 1) — cột 3, hàng 1 (0-based).

Thuật toán

Vì hình vuông đen là liên tục và đối xứng, tâm chính là trung bình cộng tọa độ của tất cả các ô đen.

1. Duyệt toàn bộ ma trận, đếm số ô đen cnt, tổng hàng X, tổng cột Y.
2. Tâm: X / cnt (hàng), Y / cnt (cột). Trả về (cột, hàng).

Code C++

#include <bits/stdc++.h>
using namespace std;

void solve(vector<vector<char>> matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    int cnt = 0, X = 0, Y = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 'B') {
                cnt++;
                X += i;
                Y += j;
            }
        }
    }
    X /= cnt;
    Y /= cnt;
    printf("%d, %d\n", Y, X);
}

int main() {
    vector<vector<char>> matrix = {
        {'W','W','B','B','B','W'},
        {'W','W','B','B','B','W'},
        {'W','W','B','B','B','W'},
        {'W','W','W','W','W','W'},
        {'W','W','W','W','W','W'}
    };
    solve(matrix);
    return 0;
}

Đầu vào / Đầu ra

Input: Ma trận như trên

Output: 3, 1