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 PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2014-04-18 18:51:32 Black Hole
TLE là sao ta @@
2014-04-10 15:11:56 Hat Dau Nho
nộp nguyên 1 bài ở 2 thời điểm!
trước thì TLE
giờ lại AC
spoj khó tính quá :)
2014-04-09 04:10:30 Hướng Thái Dương
bài này hơi bực đấy >:O cơ mà rút đc bài học nhớ đời :(((
2014-03-25 18:12:29 Bùi Xuân Thủy
một bài tạo cảm giác ức chế không hề nhẹ >"< bài thì dễ mà đề thì không rõ >"< thi acm mà thế này thì xác định :))
2014-02-24 17:37:20 Vani
Có bạn nào tốt bụng cho mình công thức QHĐ với :) mình là F[i][j] = F[i-1][j] + F[i][j-1] . Không biết đúng không?
2014-02-21 16:45:28 Vani
Các bạn cho mình hỏi tí : in ra dòng "THE GAME IS LIE" hay "THE GAME IS A LIE"

Với lại chia có dư cho 2^31 -1 là sao? không lẻ lấy kết quả chia lấy dư ta thôi à?
2013-05-10 11:02:43 an IM3 Ex-Member of Bit
Đề bài ghi là “THE GAME IS LIE” còn trong bộ test là "THE GAME IS A LIE" làm mình ko biết sai ở đâu :(
2013-01-18 13:05:02 Trần Vãn Dương D10CN2
Dung QHD + BFS
2012-11-07 11:55:27 1970 team
quy hoach dong + BFS
2012-10-28 14:41:46 Trần Vãn Dương D10CN2
OH the ha Huan Minh cung AC ne
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.