trang chủ / đề bài / icpc21_reg_e

Đường đi chẵn

Đề bài

Mô tả

Năm ngoái, Arthur tham gia Olympic Robot Việt Nam với một con robot bị trục trặc. Năm nay, cậu quyết định tham gia thêm một lần nữa.

Thử thách năm nay khó hơn nhiều. Sân chơi là một bảng hình chữ nhật kích thước r×c, gồm r hàng đánh số từ 1 đến r từ trên xuống dưới và c cột đánh số từ 1 đến c từ trái sang phải. Ô nằm ở hàng i, cột j được ký hiệu là (i,j). Mỗi ô chứa hoặc một bóng đèn, hoặc một hòn đá (không chứa cả hai). Các bóng đèn có thể bật hoặc tắt. Ban đầu, một số bóng đèn đang bật.

Mục tiêu của thử thách là tắt hết các bóng đèn. Để làm điều đó, robot của các đội có thể thực hiện một số lượt chạy. Trong mỗi lượt chạy, robot bắt đầu ở một ô bất kỳ trên bảng rồi thực hiện một dãy bước di chuyển. Một lượt chạy hợp lệ phải tuân theo các quy tắc sau:

  • Mỗi bước, robot phải di chuyển từ vị trí hiện tại sang một ô chung cạnh, tức là sang ô kế tiếp theo một trong bốn hướng: lên, xuống, trái hoặc phải.
  • Robot phải luôn ở trong bảng.
  • Robot không được đi vào ô có đá.
  • Trong một lượt chạy, robot không được đi qua một ô quá một lần. Tuy nhiên, robot có thể đi qua một ô nhiều lần trong các lượt chạy khác nhau.
  • Số ô robot đi qua trong một lượt chạy phải là số chẵn.

Từ các quy tắc trên, dễ thấy một lượt chạy hợp lệ được xác định duy nhất bởi bộ (x,y,s), trong đó (x,y) là vị trí xuất phát và s là xâu gồm các ký tự U, D, L, R mô tả dãy bước di chuyển. Ở đây U, D, L, R lần lượt là lên, xuống, trái và phải. Độ dài xâu s phải là số lẻ.

Theo luật của cuộc thi, khi thực hiện một lượt chạy, mỗi khi robot đi qua một ô, nó có thể chọn tắt đèn ở ô đó. Tuy nhiên, robot của Arthur lại bị lỗi: nó luôn đổi trạng thái đèn (đang bật thành tắt, đang tắt thành bật) ở mọi ô nó đi qua. Nói cách khác, đèn ở mọi ô trên đường đi của robot (kể cả ô xuất phát và ô kết thúc) đều bị đổi trạng thái.

Với con robot lỗi này, chỉ riêng việc tắt hết đèn đã là khó. Hãy giúp Arthur làm điều đó. Không cần tối thiểu số lượt chạy, nhưng tổng số bước di chuyển trong mọi lượt chạy không được vượt quá 106.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t: số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa hai số nguyên r và c: kích thước bảng.
  • r dòng tiếp theo mô tả bảng. Mỗi dòng là một xâu độ dài c gồm các ký tự ., X hoặc #, trong đó:
    • . là ô có đèn đang tắt,
    • X là ô có đèn đang bật,
    • # là ô có đá.

Dữ liệu ra

Với mỗi bộ dữ liệu:

  • Nếu không thể tắt hết đèn với tổng không quá 106 bước di chuyển, in ra −1.
  • Ngược lại, dòng đầu tiên chứa số nguyên k (0≤k≤106): số lượt chạy. Tiếp theo là k dòng, mỗi dòng chứa hai số nguyên x, y và một xâu s mô tả một lượt chạy như trên. Tổng độ dài các xâu không được vượt quá 106.

Nếu có nhiều cách, in ra cách bất kỳ.

Ràng buộc

  • t≤105.
  • 1≤r,c≤106.
  • Tổng r·c trên mọi bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
1
5 5
XXXXX
XXXX.
XX#X.
XXXX.
XX...
2
1 1 RRRRDDDDLLLLUUURRRDDLLU
2 5 DDDLL
Lượt thứ nhất xuất phát từ (1,1), đi hết hàng 1, xuống cột 5, quay lại theo hàng 5, lên cột 1 đến (2,1), sang phải đến (2,4), xuống (4,4), sang trái đến (4,2) rồi lên (3,2): đi qua 24 ô, sau lượt này chỉ còn đèn ở (2,5), (3,5), (4,5), (5,3), (5,4), (5,5) bật. Lượt thứ hai đi qua đúng 6 ô này.
3
1 1
X
1 3
X.X
2 2
XX
.X
-1
2
1 3 L
1 2 L
-1
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất và thứ ba có số đèn bật lẻ nên không thể tắt hết. Ở bộ thứ hai, lượt (1,3)→(1,2) tắt đèn (1,3) và bật đèn (1,2), rồi lượt (1,2)→(1,1) tắt cả hai.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0