Phân Tích Yêu Cầu Đầu Vào

Bài toán yêu cầu xác định số lượng đơn vị tàu chiến trên một ma trận lưới kích thước R x C, trong đó ký tự # đại diện cho thân tàu và . là mặt biển. Điều kiện tiên quyết là cần kiểm chứng tính hợp lệ của cấu hình bàn cờ. Một trạng thái bị coi là sai lệch nếu xuất hiện nhóm ba ký tự # xếp cạnh nhau tạo thành hình chữ T hoặc góc lệch, vi phạm nguyên tắc phân tách tàu độc lập.

Chiến Lược Thuật Toán

Linh hồn của lời giải nằm ở việc tách biệt hai nhiệm vụ riêng biệt nhưng phụ thuộc chuỗi: xác minh ràng buộc và đếm thành phần liên thông.

• Giai đoạn xác thực cấu trúc: Thay vì sử dụng nhiều câu lệnh điều kiện rẽ nhánh rời rạc, ta áp dụng cửa sổ quét 2 x 2. Duyệt qua mọi ô (i, j) đủ khoảng trống để tạo khung vuông 2 x 2 (từ 0 đến R-2 và C-2). Tính tổng số ô mang giá trị # trong khung này. Nếu tổng bằng 3, tức là tồn tại sự chồng chéo hoặc góc nhọn bất hợp lệ, thuật toán trả về mã lỗi ngay lập tức.
• Giai đoạn truy vết liên kết: Khi dữ liệu đầu vào vượt qua bước kiểm tra, bài toán trở thành bài toán chuẩn tìm số thành phần liên thông trên đồ thị. Khởi tạo ma trận trạng thái visited ban đầu là false. Duyệt tuần tự từng ô lưới. Khi gặp ô chứa # và chưa được đánh dấu, kích hoạt hàm đệ quy DFS để lan tỏa và đánh dấu lại toàn bộ các ô thuộc cùng một con tàu. Mỗi lần hoàn tất một chuỗi truy vết, increment bộ đếm số lượng tàu.

Tối Ưu Hóa Triển Khai Mã Nguồn

Các phiên bản code dưới đây được viết lại hoàn toàn nhằm cải thiện khả năng bảo trì và hiệu năng运行时. Ma trận ban đầu được chuyển đổi thành mảng chuỗi (vector<string> / List<String>) để đọc dữ liệu nhanh hơn. Hướng di chuyển trong hàm duyệt được điều chỉnh sang chuẩn 4 hướng (đệ quy thuần túy), loại bỏ các lỗi biên giới và di chuyển đường chéo dư thừa thường gặp trong các bản sao cũ. Tên biến và hàm được đặt theo chuẩn ngữ nghĩa kỹ thuật rõ ràng.

C++ Implementation

#include <iostream>
#include <vector>
using namespace std;

vector<string> gameBoard;
vector<vector<bool>> cellVisited;
int totalRows, totalCols;

// Kiểm tra tính hợp lệ của bàn cờ bằng cửa sổ trượt 2x2
bool validateBoardConfiguration() {
    for (int i = 0; i < totalRows - 1; ++i) {
        for (int j = 0; j < totalCols - 1; ++j) {
            int occupiedCells = 0;
            if (gameBoard[i][j] == '#') occupiedCells++;
            if (gameBoard[i + 1][j] == '#') occupiedCells++;
            if (gameBoard[i][j + 1] == '#') occupiedCells++;
            if (gameBoard[i + 1][j + 1] == '#') occupiedCells++;
            
            // 3 ô trong khung 2x2 cấu thành hình chữ T hoặc góc nhọn => Sai đặt
            if (occupiedCells == 3) return false;
        }
    }
    return true;
}

// Hàm DFS tiêu chuẩn 4 hướng để đánh dấu thành phần liên thông
void traceConnectedShip(int row, int col) {
    cellVisited[row][col] = true;
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    
    for (int k = 0; k < 4; ++k) {
        int nextR = row + dr[k];
        int nextC = col + dc[k];
        
        if (nextR >= 0 && nextR < totalRows &&
            nextC >= 0 && nextC < totalCols &&
            !cellVisited[nextR][nextC] && 
            gameBoard[nextR][nextC] == '#') {
            traceConnectedShip(nextR, nextC);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    if (!(cin >> totalRows >> totalCols)) return 0;
    
    gameBoard.resize(totalRows);
    cellVisited.assign(totalRows, vector<bool>(totalCols, false));
    for (int i = 0; i < totalRows; ++i) cin >> gameBoard[i];
    
    if (!validateBoardConfiguration()) {
        cout << "Bad placement." << "\n";
        return 0;
    }
    
    int independentShips = 0;
    for (int i = 0; i < totalRows; ++i) {
        for (int j = 0; j < totalCols; ++j) {
            if (gameBoard[i][j] == '#' && !cellVisited[i][j]) {
                traceConnectedShip(i, j);
                independentShips++;
            }
        }
    }
    
    cout << "There are " << independentShips << " ships." << "\n";
    return 0;
}

Java Implementation

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    static ArrayList<String> gameBoard;
    static boolean[][] cellVisited;
    static int totalRows, totalCols;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        if (!scanner.hasNextInt()) return;
        
        totalRows = scanner.nextInt();
        totalCols = scanner.nextInt();
        
        gameBoard = new ArrayList<>();
        for (int i = 0; i < totalRows; i++) gameBoard.add(scanner.next());
        
        cellVisited = new boolean[totalRows][totalCols];
        
        if (!validateBoardConfiguration()) {
            System.out.println("Bad placement.");
            return;
        }
        
        int independentShips = 0;
        for (int i = 0; i < totalRows; i++) {
            for (int j = 0; j < totalCols; j++) {
                if (gameBoard.get(i).charAt(j) == '#' && !cellVisited[i][j]) {
                    traceConnectedShip(i, j);
                    independentShips++;
                }
            }
        }
        
        System.out.println("There are " + independentShips + " ships.");
    }
    
    private static boolean validateBoardConfiguration() {
        for (int i = 0; i < totalRows - 1; i++) {
            for (int j = 0; j < totalCols - 1; j++) {
                int occupiedCells = 0;
                if (gameBoard.get(i).charAt(j) == '#') occupiedCells++;
                if (gameBoard.get(i + 1).charAt(j) == '#') occupiedCells++;
                if (gameBoard.get(i).charAt(j + 1) == '#') occupiedCells++;
                if (gameBoard.get(i + 1).charAt(j + 1) == '#') occupiedCells++;
                
                if (occupiedCells == 3) return false;
            }
        }
        return true;
    }
    
    private static void traceConnectedShip(int row, int col) {
        cellVisited[row][col] = true;
        int[] dRow = {-1, 1, 0, 0};
        int[] dCol = {0, 0, -1, 1};
        
        for (int k = 0; k < 4; k++) {
            int nextR = row + dRow[k];
            int nextC = col + dCol[k];
            
            if (nextR >= 0 && nextR < totalRows &&
                nextC >= 0 && nextC < totalCols &&
                !cellVisited[nextR][nextC] && 
                gameBoard.get(nextR).charAt(nextC) == '#') {
                traceConnectedShip(nextR, nextC);
            }
        }
    }
}