Phân tích: Rotate

Đây là một bài toán mô phỏng tương đối đơn giản: đề bài cho biết cần làm gì, và ta chỉ cần thực hiện đúng như vậy.

Tuy nhiên, có một điểm thú vị. Tên bài là Rotate và đề bài nói rất nhiều về phép xoay, nhưng đó lại chính là thứ duy nhất ta không cần cài đặt! Xoay bảng \(90\) độ theo chiều kim đồng hồ rồi đẩy mọi quân xuống dưới có tác dụng giống hệt việc không xoay mà đẩy mọi quân sang phải. Miễn là đẩy các quân theo đúng hướng, việc có thực sự xoay bảng hay không không quan trọng. Mọi dãy \(K\) quân liên tiếp đều tương ứng như nhau trong hai hình, nên kết quả xuất ra cũng giống nhau.

Vì vậy, một lời giải đơn giản gồm các bước sau.

1. Đẩy mọi quân sang phải

Trong từng hàng, dồn tất cả các quân sang phía bên phải. Có thể thực hiện bằng đoạn mã như sau:

    for (int row = 1; row < n; ++row) {
      int x = n-1;
      for (int col = n-1; col >= 0; col--) 
        if (piece[row][col] != '.') {
          piece[row][x] = piece[row][col]; x--;
        }
      while(x>=0) {piece[row][x]='.'; x--;}
    }

2. Kiểm tra dãy \(K\) quân cùng màu

Kiểm tra xem có \(K\) quân cùng màu nằm liên tiếp hay không. Có những mẹo để tăng tốc bước này, nhưng trong bài này \(N\) không vượt quá \(50\), nên không cần tối ưu đặc biệt. Từ mỗi quân, ta có thể bắt đầu kiểm tra theo cả 8 hướng; hoặc chỉ cần 4 hướng nhờ tính đối xứng. Với mỗi hướng, đi \(K\) bước kể từ quân xuất phát và xem tất cả các quân gặp trên đường có cùng màu hay không. Cách viết phần đi từng bước theo một hướng và kiểm tra xem vị trí có ra ngoài bảng hay không sẽ khá giống nhau trong nhiều ngôn ngữ lập trình khác nhau.

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức của Google Code Jam 2010 - Rotate, thuộc kho Google Coding Competitions (Apache-2.0).