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
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
.(ô trống) hoặc lào(đồng xu).Output
Example
Test 1
Input
Output