CSES - Coin Grid | Lưới xu

Xem PDF

Điểm: 1800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một bảng \(n × n\) mà mỗi ô vuông có thể là ô trống hoặc có một đồng xu trên đó. Với mỗi lần di chuyển, bạn có thể loại bỏ tất cả các đồng xu trong một hàng hoặc cột.

Số lần di chuyển ít nhất để dọn sạch cả bảng là bao nhiêu?

Input

  • Dòng đầu tiên gồm số nguyên \(n\): kích thước của bảng. Các hàng và cột được đánh số \(1, 2,..., n\).
  • \(n\) dòng tiếp theo mô tả cách sắp xếp của bảng. Mỗi dòng gồm \(n\) kí tự: mỗi kí tự có thể là . (ô trống) hoặc là o (đồng xu).

Output

  • Đầu tiên in ra số nguyên \(k\): số lần di chuyển ít nhất thoả mãn. Sau đó, in ra \(k\) dòng mô tả các bước di chuyển.
  • Trên mỗi dòng, trước hết in ra 1 (hàng) hoặc 2 (cột), sau đó in số thứ tự của hàng hoặc cột cần di chuyển. Bạn có thể in ra bất kỳ phương án phù hợp.

Constraints

  • \(1 \le n \le 100\)

Example

Sample input

3
..o
o.o
...

Sample output

2
1 2
2 3


Bình luận


  • 0
    Thanh72    9:52 p.m. 20 Tháng 8, 2023

    Cho một bảng \(n \times n\) với mỗi ô vuông có thể là ô trống hoặc có một đồng xu trên đó. Với mỗi bước, bạn có thể loại bỏ tất cả các đồng xu trong một hàng hoặc cột.

    Số bước ít nhất để loại bỏ tất cả các đồng xu cả bảng là bao nhiêu?

    Input

    • Dòng đầu tiên gồm số nguyên dương \(n(n \leq 100)\): kích thước của bảng. Các hàng và cột được đánh số \(1, 2, ..., n\).
    • \(n\) dòng tiếp theo mô tả của bảng. Mỗi dòng gồm \(n\) kí tự: mỗi kí tự có thể là . (ô trống) hoặc là o (đồng xu).

    Output

    • Đầu tiên in ra số nguyên \(k\): số lần di chuyển ít nhất thoả mãn. Sau đó, in ra \(k\) dòng mô tả các bước.
    • Trên mỗi dòng, in ra 1 (hàng) hoặc 2 (cột), sau đó in số thứ tự của hàng hoặc cột được chọn. Bạn có thể in ra bất kỳ phương án phù hợp.

    Example

    Test 1

    Input
    3
    ..o
    o.o
    ...
    Output
    2  
    1 2  
    2 3