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.|

BCROBOT - Đường đi rô-bốt

 

Bạn vừa tạo ra một bảng để cho rô-bốt có thể tìm đường đi từ ô ở trên cùng – bên trái (ô xuất phát) đến ô ở dưới cùng – bên phải (ô đích). Tuy nhiên, do quên mất một số skill AI mà bạn chỉ lập trình cho rô-bốt có thể đi sang phải 1 ô hoặc xuống dưới 1 ô. Bạn đặt một số chướng ngại vật trên các ô của bảng (dĩ nhiên là rô-bốt ko thể đi vào các ô này), sau đó bạn ngồi quan sát. Tuy nhiên, sau một thời gian, bạn cảm thấy mệt mỏi vì nó bị mắc kẹt và bạn tự hỏi: “Có bao nhiêu đường đi có thể cho rô-bốt từ ô xuất phát tới ô đích” và “Nếu không có, thì liệu rô-bốt có thể đến ô đích nếu nó được lập trình có thể đi lên trên 1 ô và sang trái 1 ô”.

Vì vậy, bạn quyết định viết 1 chương trình, cho kích thước của bảng n×n với các chướng ngại vật đã được dánh dấu mà rô-bốt không thể đi tới. Đếm số đường đi khác nhau mà rô-bốt có thể đi từ ô xuất phát tới ô đích. Và nếu không có đường đi, bạn phải kiếm tra xem có thể đi từ ô xuất phát tới ô đích nếu có thể sang trái và lên trên. Tuy nhiên, chương trình của bạn không xử lý các số rất lớn, do đó, kết quả phải được lấy dư cho 2^31-1.

Dữ liệu:

Dòng đầu tiên chứa một số nguyên n (1 <= n <= 1000).

N dòng sau, mỗi dòng chứa n kí tự đại, mỗi kí tự diện cho một ô của bảng. Kí tự có thể là ‘.’ hoặc ‘#’. Kí tự ‘.’ nếu ô đó có thể đi, hoặc ‘#’ nếu ô đó là chướng ngại vật. Không có trường hợp có chướng ngại vật ở ô xuất phát và ô đích.  

Kết quả:

In ra một dòng chứa số nguyên là số đường đi khác nhau từ ô xuất phát tới ô kết thúc (lấy dư cho 2^31-1) hoặc “THE GAME IS A LIE” nếu không thể đi từ ô xuất phát tới ô kết thúc bằng cách chỉ sang phải và xuống dưới nhưng có thể đi nếu chấp nhận thêm cách đi lên trên và sang trái, hoặc INCONCEIVABLE nếu đơn giản là không có đường đi từ ô xuất phát tới ô đích.

Ví dụ:

INPUT

OUTPUT

5

.....

#..#.

#..#.

...#.

.....

6


INPUT

OUTPUT

7

......#

####...

.#.....

.#...#.

.#.....

.#..###

.#.....

THE GAME IS A LIE

 

 


ID RESULT TIME
code...



Được gửi lên bởi:adm
Ngày:2012-01-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2012-10-28 14:41:46 Trần Vãn Dương D10CN2
OH the ha Huan Minh cung AC ne
2012-10-27 12:30:14 Vương Sỹ Huấn DH BK TP HCM
Bai nay su dung hai ki thuat moi AC duoc
2012-10-16 13:53:26 LOVE
Anh Hữu Thắng D10Cn4 ơi em chưa hiểu bài TRái Tim của DẤt nước Anh làm Được bài đó có gì anh commen lại giúp mọi người hiểu Đề bài rồi chúng ta cùng làm Dược không anh

Last edit: 2012-10-16 13:55:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.