Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FINDEXIT - Tìm đường thoát khoải Mê cung

Bản đồ một mê cung hình chữ nhật được chia thành lưới ô vuông kích thước mxn, trên mỗi ô (i, j) ghi một ký tự aij:

  • aij = '.' nếu ô đó là ô an toàn
  • aij = 'E' nếu là ô có một nhà thám hiểm đang đứng, có đúng một ô ghi chữ "E".
  • aij = 'X' nếu đó là ô nguy hiểm.

Tại mỗi thời điểm, nhà thám hiểm chỉ được di chuyển sang một trong các ô an toàn kề cạnh với ô đang đứng.

Yêu cầu: Hãy tìm hành trình di chuyển giúp cho nhà thám hiểm thoát ra một ô nằm ở biên của mê cung.

Dữ liệu vào:

  • Dòng 1: Chứa hai số m, n cách nhau ít nhất một dấu cách.
  • m dòng tiếp theo, dòng thứ i chứa n ký tự, ký tự thứ jaij.

Dữ liệu ra:

  • Dòng 1: Ghi từ YES hay NO tuỳ theo có tồn tại đường đi thoát khỏi mê cung hay không.
  • Nếu dòng 1 ghi từ YES, các dòng tiếp theo, mỗi dòng ghi chỉ số hàng và chỉ số cột của một ô trong hành trình cách nhau ít nhất một dấu cách. Các ô trên đường đi phải được liệt kê theo đúng thứ tự đi qua, bắt đầu từ ô mà nhà thám hiểm đang đứng tới ô biên kết thúc hành trình, không có ô nào được lặp lại trong hành trình. Nếu có nhiều hành trình thỏa mãn thì ghi ra một hành trình bất kỳ.

Ví dụ:

Dữ liệu vào:
10 10
XXXXXXXXXX
XXXXXXXXXX
XX.....XXX
XX.XXX.XXX
XX.EXX...X
XXXXXX.X.X
.......X.X
XXXXXXXX.X
.........X
XXXXXXXXXX
Dữ liệu ra:
YES
5 4
5 3
4 3
3 3
3 4
3 5
3 6
3 7
4 7
5 7
6 7
7 7
7 6
7 5
7 4
7 3
7 2
7 1

Giới hạn: 1 ≤ n ≤ 100.

 


Được gửi lên bởi:noname00.pas
Ngày:2017-10-18
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.