Link Sub: http://www.spoj.com/PTIT/problems/BCROBOT/
Người Gửi: Dương Lee
- Problem:
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.
InputVì 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ò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.
Output
Example:
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.
Input
5
.....
#..#.
#..#.
...#.
.....
Output:
6
Input
7
......#
####...
.#.....
.#...#.
.#.....
.#..###
.#.....
Output:
THE GAME IS A LIE
- Solution:
Input
7
......#
####...
.#.....
.#...#.
.#.....
.#..###
.#.....
Output:
THE GAME IS A LIE
- Đối với trường hợp đếm số đường đi ta sẽ dùng QHĐ F[i][j] = F[i-1]+F[i][j-1] (Vì chỉ số cách đi đến ô [i,j]=số cách đi từ trái sang và số cách đi từ trên xuống)
- Đối với trường hợp tìm xem có đường đi từ nếu cho phép đi lên trên và xuống dưới: ta sẽ dùng BFS để kiểm tra xem mảng check có duyệt qua ô [n,n] hay không?
- Đối với trường hợp tìm xem có đường đi từ nếu cho phép đi lên trên và xuống dưới: ta sẽ dùng BFS để kiểm tra xem mảng check có duyệt qua ô [n,n] hay không?
- Code:
C++:
https://ideone.com/D94X0C
#include <iostream>
#include <math.h>
#include <queue>
using namespace std;
#define Du 2147483647
int n;
char arr[1003][1003];
void read ()
{
cin>>n;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
cin>>arr[i][j];
}
}
}
long long F[1003][1003];
int check[1003][1003];
void init()
{
for (int i=0; i<=n; i++)
{
for (int j=0; j<=n; j++)
{
F[i][j] = 0;
check[i][j]=0;
}
}
}
long long count ()
{
F[1][0]=1;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (arr[i][j]=='.')
F[i][j]=(F[i-1][j]+F[i][j-1])%Du;
}
}
return F[n][n];
}
struct data
{
int i;
int j;
};
int x_xq[]={-1, +0, +1, +0};
int y_xq[]={+0, +1, +0, -1};
void BFS (int y, int x)
{
data tmp;
tmp.i = y;
tmp.j = x;
queue <data> q;
q.push(tmp);
check[y][x]=1;
while (!q.empty())
{
data u = q.front();
q.pop();
for (int i=0; i<4; i++)
{
int x_m = u.j+x_xq[i];
int y_m = u.i+y_xq[i];
if (x_m>=1 && x_m<=n && y_m>=1 && y_m<=n && check[y_m][x_m]==0 && arr[y_m][x_m]=='.')
{
tmp.i = y_m;
tmp.j = x_m;
q.push(tmp);
check[y_m][x_m] = 1;
}
}
}
}
int main ()
{
read();
init();
long long x = count();
if (x!=0)
cout<<x;
else
{
BFS(1, 1);
if (check[n][n]==1)
cout<<"THE GAME IS A LIE";
else
cout<<"INCONCEIVABLE";
}
return 0;
}JAVA:
...Python:
...
