Link Sub: http://www.spoj.com/PTIT/problems/PTIT017K/
Người Gửi: Dương Lee
- Problem:
Xét lưới ô vuông vô hạn trong đó có một số ô cấm, các ô còn lại là tự do. Các dòng và cột của lưới được đánh số theo thứ tự bởi các số nguyên … -3 -2 -1 0 1 2 3 … Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng theo thứ tự từ dưới lên trên. Ô nằm trên giao của dòng x và cột y được gọi là ô (x, y). Một quân mã đặt ở ô xuất phát là ô (0,0). Sau một bước đi, ta có thể di quân mã đến một trong các ô ở đỉnh đối diện trên đường chéo của hình chữ nhật kích thước 2×3.
Luật di chuyển của quân mã
Yêu cầu: Cho biết toạ độ của các ô cấm, vị trí ô đích nơi quân mã cần đến, hãy tìm cách di chuyển quân mã từ ô (0,0) đến ô đích sao cho số lượng bước đi cần thực hiện là ít nhất.
Input
X
|
X
| |||||
X
|
X
| |||||
M
| ||||||
X
|
X
| |||||
X
|
X
| |||||
Yêu cầu: Cho biết toạ độ của các ô cấm, vị trí ô đích nơi quân mã cần đến, hãy tìm cách di chuyển quân mã từ ô (0,0) đến ô đích sao cho số lượng bước đi cần thực hiện là ít nhất.
Dòng đầu tiên chứa T (T ≤ 3) là số lượng test, tiếp đến là T nhóm dòng, mỗi nhóm chứa dữ liệu về một test theo khuôn dạng sau:
Dòng đầu tiên chứa 2 số nguyên xt, yt được ghi cách nhau bởi dấu cách cho biết toạ độ của ô đích là (xt, yt);
Dòng thứ hai chứa số nguyên dương n (n ≤ 1000) là số lượng ô cấm;
Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách xi, yi cho biết (xi, yi) là toạ độ của ô cấm thứ i (i = 1, 2, …, n).
Dòng đầu tiên chứa 2 số nguyên xt, yt được ghi cách nhau bởi dấu cách cho biết toạ độ của ô đích là (xt, yt);
Dòng thứ hai chứa số nguyên dương n (n ≤ 1000) là số lượng ô cấm;
Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách xi, yi cho biết (xi, yi) là toạ độ của ô cấm thứ i (i = 1, 2, …, n).
Output
Example:
Gồm T dòng mỗi dòng chứa kết quả của một test tương ứng trong dữ liệu vào là số lượng bước đi ít nhất cần thực hiện để di chuyển quân mã từ ô xuất phát (0,0) đến ô đích. Ghi số −1 nếu như không thể di chuyển quân mã đến ô đích.
Input
1
2 4
0
Output:
2
- Solution:
- Bài này cho lưới ô vuông vô hạn nhưng thực ra tối đa chỉ có nằm trong khoảng -1000->1000, và max khoảng tầm 1000 điểm cấm. Nên căng lắm lưới cỡ 10^5 là có thể tìm thấy đường đi đến điểm cần tìm rồi.
- Nhưng các điểm còn có cả tọa độ âm nên khó cho việc biểu diễn trên máy. Nên mình quy về các đỉnh, mỗi ô là đại diện cho một đỉnh.
Công thức chuyển: "(2*y_max*y_max + 3*y_max - x_max + 1) + (2*y_max + 1)*y + x". Công thức này thực ra chỉ là tính diện tích thôi, các bạn có thể tự thiết lập.
- Nhưng vấn đề lại đặt ra đó là: (10^5*10^5+1)^2 đỉnh thì không một cấu trúc tuần tự nào (arr, vector) chứa nổi -> Mình quyết định chuyển sang "map" có cấu trúc liên kết để giải quyết vần đề này.
- Cuối cùng là chỉ việc BFS kết hợp với map nữa là ok.
- Nhưng các điểm còn có cả tọa độ âm nên khó cho việc biểu diễn trên máy. Nên mình quy về các đỉnh, mỗi ô là đại diện cho một đỉnh.
Công thức chuyển: "(2*y_max*y_max + 3*y_max - x_max + 1) + (2*y_max + 1)*y + x". Công thức này thực ra chỉ là tính diện tích thôi, các bạn có thể tự thiết lập.
- Nhưng vấn đề lại đặt ra đó là: (10^5*10^5+1)^2 đỉnh thì không một cấu trúc tuần tự nào (arr, vector) chứa nổi -> Mình quyết định chuyển sang "map" có cấu trúc liên kết để giải quyết vần đề này.
- Cuối cùng là chỉ việc BFS kết hợp với map nữa là ok.
- Code:
C++:
https://ideone.com/HY9CiO
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <map>
#include <queue>
using namespace std;
const long long x_max = 100000;
const long long y_max = 100000;
#define ll long long
int inSide (ll x, ll y)
{
if (x>=-x_max && x<=x_max && y>=-y_max && y<=y_max)
return 1;
return 0;
}
ll vertex (ll x, ll y)
{
return (2*y_max*y_max + 3*y_max - x_max + 1) + (2*y_max + 1)*y + x;
}
ll x_t, y_t;
ll n;
ll x_i, y_i;
map <ll, char> prevent;
void read ()
{
scanf ("%lld%lld", &x_t, &y_t);
scanf ("%lld", &n);
for (ll i=0; i<n; i++)
{
scanf ("%lld%lld", &x_i, &y_i);
prevent[vertex(x_i, y_i)] = 'X';
}
}
map <ll, char> check;
map <ll, ll> len;
void init ()
{
prevent.clear();
check.clear();
len.clear();
}
struct data
{
ll x, y;
data (ll x_, ll y_)
{
x = x_;
y = y_;
}
};
ll x_xq[] = {-1, -2, -2, -1, +1, +2, +2, +1};
ll y_xq[] = {-2, -1, +1, +2, +2, +1, -1, -2};
void BFS (ll x, ll y)
{
queue <data> q;
q.push(data(x, y));
check[vertex(x, y)] = 'Y';
len[vertex(x, y)] = 0;
while (!q.empty())
{
data v = q.front();
q.pop();
for (int i=0; i<8; i++)
{
ll x_p = v.x+x_xq[i];
ll y_p = v.y+y_xq[i];
if (inSide(x_p, y_p)==1 && check[vertex(x_p, y_p)]!='Y' && prevent[vertex(x_p, y_p)]!='X')
{
q.push(data(x_p, y_p));
len[vertex(x_p, y_p)] = len[vertex(v.x, v.y)]+1;
check[vertex(x_p, y_p)] = 'Y';
if (x_p == x_t && y_p == y_t) return;
}
}
}
}
int main ()
{
int t;
scanf ("%d", &t);
while (1)
{
if (t==0) break;
t--;
init();
read();
BFS(0, 0);
printf("%lld\n", len[vertex(x_t, y_t)]);
}
return 0;
}JAVA:
...Python:
...