Editorial for gundam: Đừng động vào Gundam của anh Hiếu

Hiểu bài toán

Bài toán yêu cầu đếm số cách đặt một chiếc giường có kích thước 1x2 vào trong một phòng được biểu diễn bởi ma trận N x M. Các ô trống có thể đặt giường là dấu '.' và các chướng ngại vật là dấu '#'. Giường có thể đặt theo chiều ngang (chiếm 2 ô liền kề cùng hàng) hoặc chiều dọc (chiếm 2 ô liền kề cùng cột). Mỗi cách đặt hợp lệ phải nằm hoàn toàn trong khu vực trống của phòng.

Các cách tiếp cận

Cách Duyệt theo hàng và cột riêng biệt

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int main()
{
    char a[100][100];
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 0; i<n; i++)
    {
        scanf("%s", &a[i]);
    }
    int ngang = 0, doc = 0;
    // Đếm giường nằm ngang
    for(int i = 0; i<n; i++)
    {
        for(int j = 0; j < m - 1; j++)
        {
            if(a[i][j] == '.' && a[i][j+1] == '.')
                ngang++;
        }
    }
    // Đếm giường nằm dọc
    for(int i = 0; i<m; i++)
    {
        for(int j = 0; j<n-1; j++)
        {
            if(a[j][i] == '.' && a[j+1][i] == '.')
                doc++;
        }
    }
    printf("%d", doc + ngang);
    return 0;
}

• Time Complexity: O(N * M)
• Space Complexity: O(N * M)

Cách tiếp cận này chia vấn đề thành hai phần riêng biệt: đếm các cặp ô trống nằm ngang và đếm các cặp ô trống nằm dọc. Vòng lặp đầu tiên duyệt qua từng hàng (N hàng), và với mỗi hàng, duyệt qua từng cặp ô kề nhau từ cột 0 đến M-2. Nếu cả hai ô đều là '.', ta tăng biến đếm 'ngang'. Vòng lặp thứ hai duyệt qua từng cột (M cột), và với mỗi cột, duyệt qua các cặp ô kề nhau từ hàng 0 đến N-2. Nếu cả hai ô đều là '.', ta tăng biến đếm 'doc'. Kết quả cuối cùng là tổng của hai biến này.

Cách Duyệt đơn lẻ (One-pass)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int main() {
    char str[100][100];
    int m,n;
    scanf("%d %d",&m,&n);
    for (int i = 0;i < m;i++){
        for (int j = 0;j < n;j++){
            scanf(" %c",&str[i][j]);
        }
    }
    int count = 0;
    for (int i = 0;i < m;i++){
        for (int j = 0;j < n;j++){
            // Kiểm tra giường nằm ngang (phải)
            if (j < n-1 && str[i][j] == '.' && str[i][j+1] == '.') count++;
            // Kiểm tra giường nằm dọc (dưới)
            if (i < m-1 && str[i][j] == '.' && str[i+1][j] == '.') count++;
        }
    }
    printf("%d",count);
}

• Time Complexity: O(N * M)
• Space Complexity: O(N * M)

Phương pháp này thực hiện duyệt qua mỗi ô ('.') chỉ một lần duy nhất. Tại mỗi ô (i, j), nó kiểm tra xem có thể đặt giường theo chiều ngang sang phải (tại cột j và j+1) hay chiều dọc xuống dưới (tại hàng i và i+1) hay không. Nếu có, ta cộng vào biến đếm. Cách này tổng hợp cả việc đếm giường ngang và giường dọc trong cùng một cấu trúc vòng lặp kép.

Cách Tối ưu hóa Input/Output (C style)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#include<math.h>


int main(){
    int m,n;
    scanf("%d%d",&n,&m);
    getchar();
    char a[n][m];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) scanf("%c",&a[i][j]);
        getchar();
    }
    int dem=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m-1;j++){
            if(a[i][j]=='.'&&a[i][j+1]=='.')dem++;
        }
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]=='.'&&a[i+1][j]=='.')dem++;
        }
    }
    printf("%d",dem);
}

• Time Complexity: O(N * M)
• Space Complexity: O(N * M)

Đây là cách tiếp cận tương tự Approach 1, nhưng chú trọng vào việc xử lý đầu vào. Sử dụng getchar() để xử lý các ký tự newline thừa sau khi nhập N, M và sau mỗi dòng ma trận. Việc khai báo mảng char a[n][m] với kích thước biến là một mở rộng của tiêu chuẩn C99 (VLA). Logic đếm vẫn tách biệt giữa giường ngang và giường dọc.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia nhỏ thành việc đếm các cặp ô trống liền kề theo chiều ngang và chiều dọc một cách độc lập.
• Mỗi cách đặt giường tương ứng với một cặp ô trống liền kề. Do đó, số cách đặt giường chính là tổng số cặp ô trống liền kề (ngang + dọc).
• Chỉ cần duyệt qua các ô và kiểm tra ô bên phải và ô bên dưới là đủ để đếm hết các trường hợp mà không bị lặp.

Lỗi thường gặp

• Lỗi thứ tự nhập N, M: Đề bài thường cho N (số hàng) rồi M (số cột), nhưng giải pháp C++ hoặc C có thể cần chú ý thứ tự khai báo mảng (ví dụ: char a[N][M] hay char a[M][N]). Trong các giải pháp mẫu, biến m và n được gán ngược để phù hợp với khai báo mảng.
• Sai lệch biên: Khi kiểm tra ô kề nhau, phải đảm bảo chỉ số không vượt quá biên của ma trận (ví dụ: j < n-1 hoặc i < m-1).
• Xử lý ký tự newline: Khi dùng scanf với char, các ký tự newline (\n) có thể gây lỗi nếu không được xử lý đúng cách, dẫn đến việc nhập sai ma trận. Giải pháp sample 3 sử dụng getchar() để giải quyết vấn đề này.