diff options
| -rw-r--r-- | others/other/README.md | 41 | ||||
| -rw-r--r-- | others/other/vdd.cpp | 161 |
2 files changed, 202 insertions, 0 deletions
diff --git a/others/other/README.md b/others/other/README.md index 86d49f8..0d4198b 100644 --- a/others/other/README.md +++ b/others/other/README.md @@ -938,3 +938,44 @@ Một dòng duy nhất chứa số đơn vị khối nước đọng lại. | NUOC.INP | NUOC.OUT | | -------------------------------------------------------------------- | :------: | | 5 5<br>9 9 9 9 9<br>9 2 2 2 9<br>9 2 5 2 9<br>9 2 2 2 9<br>9 9 9 9 9 | 60 | + +## Vượt đại dương + +Bản đồ của một vùng biển được cho bởi một lưới các ô vuông đơn vị gồm N dòng, N +cột (N ≤ 100), trong đó vùng biển được đánh số 0 và các vùng khác được đánh số +1\. Giả sử rằng bên ngoài biên của lưới là đại dương mênh mông. Một hòn đảo là +một tập các ô vuông có giá trị 1 và có chung cạnh với nhau, số các ô vuông này +chính là diện tích của hòn đảo. + +Một ngư dân sống trên một hòn đảo sẽ vượt biển tìm đến một hòn đảo mới rộng lớn +hơn để sinh sống. Từ một ô vuông trên bản đồ, anh ta chỉ được đến một ô khác +chung cạnh với ô vuông mà anh ta đang đứng (cả trên cạn lẫn dưới biển). Khi +vượt đại dương anh ta không muốn dừng chân trên một hòn đảo nào khác ngoài hòn +đảo mà anh ta muốn đến. + +### Yêu cầu + +Cho trước bản đồ của vùng biển và vị trí của anh ngư dân, hãy cho biết có một +hòn đảo nào khác có diện tích lớn hơn diện tích hòn đảo mà anh ngư dân đang +sinh sống. Nếu có hãy chỉ giúp anh ngư dân một hành trình vượt biển đến một hòn +đảo lớn hơn sao cho đoạn đường vượt biển là ngắn nhất. Nếu với cùng độ dài đoạn +đường đó mà có thể đến được các đảo khác nhau thì ưu tiên đến đảo có diện tích +lớn nhất. + +### Dữ liệu + +* Dòng đầu ghi số N cho biết kích thước bản đồ, hai số x, y là vị trí dòng và + cột trên bản đồ nơi mà anh ngư dân đang sinh sống. +* N dòng tiếp theo, mỗi dòng ghi N số cho biết nội dung bản đồ các số trên cùng + một dòng cách nhau ít nhất một khoảng trắng. + +### Kết quả + +* Nếu không tìm được một hòn đảo thích hợp thì ghi số 0. +* Nếu tìm được thì ghi độ dài của hành trình. + +### Ví dụ + +| VDD.INP | VDD.OUT | +| ---------------------------------------------------------------------- | :-----: | +| 5 1 5<br>0 0 0 1 1<br>0 0 0 0 1<br>1 1 0 0 1<br>1 1 0 0 0<br>0 1 0 0 0 | 2 | diff --git a/others/other/vdd.cpp b/others/other/vdd.cpp new file mode 100644 index 0000000..5743bbb --- /dev/null +++ b/others/other/vdd.cpp @@ -0,0 +1,161 @@ +#include <cstdlib> +#include <iostream> +#include <fstream> +#include <queue> +#include <vector> +#include <functional> +using namespace std; + +#define POINT(x, y) (((x) << 7) + (y)) +#define ENC(s, x, y) (((s) << 14) + ((x) << 7) + (y)) + +void +explore(short x, short y, short n, short a[102][102], short* p[102][102]) +{ + short i, j; + short* area = p[x][y]; + queue<short> q; + q.push(POINT(x, y)); + + while (!q.empty()) + { + i = q.front(); + q.pop(); + j = i & 127; + i >>= 7; + + if (i > 1 && a[i - 1][j] && !p[i - 1][j]) + { + (*area)++; + p[i - 1][j] = area; + q.push(POINT(i - 1, j)); + } + if (i < n && a[i + 1][j] && !p[i + 1][j]) + { + (*area)++; + p[i + 1][j] = area; + q.push(POINT(i + 1, j)); + } + if (j > 1 && a[i][j - 1] && !p[i][j - 1]) + { + (*area)++; + p[i][j - 1] = area; + q.push(POINT(i, j - 1)); + } + if (j < n && a[i][j + 1] && !p[i][j + 1]) + { + (*area)++; + p[i][j + 1] = area; + q.push(POINT(i, j + 1)); + } + } +} + +int +main() +{ + short n, x, y, i, j, a[102][102] = {}; + ifstream infile; + infile.open("VDD.INP"); + infile >> n >> x >> y; + for (i = 1; i <= n; i++) + for (j = 1; j <= n; j++) + infile >> a[i][j]; + infile.close(); + + short* p[102][102] = {}; + for (i = 1; i <= n; i++) + for (j = 1; j <= n; j++) + if (a[i][j] && !p[i][j]) + { + p[i][j] = (short*) malloc(sizeof(short)); + *p[i][j] = 1; + explore(i, j, n, a, p); + } + + priority_queue<long, vector<long>, greater<long>> heap; + bool visited[102][102] = {}; + queue<short> q; + visited[x][y] = true; + q.push(POINT(x, y)); + while (!q.empty()) + { + i = q.front(); + q.pop(); + j = i & 127; + i >>= 7; + if (!(a[i + 1][j] && a[i][j + 1] && a[i - 1][j] && a[i][j - 1])) + heap.push(POINT(i, j)); + + if (i > 1 && !visited[i - 1][j] && a[i - 1][j]) + { + q.push(POINT(i - 1, j)); + visited[i - 1][j] = true; + } + if (i < n && !visited[i + 1][j] && a[i + 1][j]) + { + q.push(POINT(i + 1, j)); + visited[i + 1][j] = true; + } + if (j > 1 && !visited[i][j - 1] && a[i][j - 1]) + { + q.push(POINT(i, j - 1)); + visited[i][j - 1] = true; + } + if (j < n && !visited[i][j + 1] && a[i][j + 1]) + { + q.push(POINT(i, j + 1)); + visited[i][j + 1] = true; + } + } + + short* current = p[x][y], s = 12345; + long tmp; + while (!heap.empty()) + { + tmp = heap.top(); + heap.pop(); + i = tmp >> 7 & 127; + j = tmp & 127; + tmp >>= 14; + if (tmp > s) + break; + if (p[i][j] && p[i][j] != current) + if (*p[i][j] <= *current) + continue; + else + { + s = tmp; + *current = *p[i][j]; + } + + tmp++; + if (i && !visited[i - 1][j]) + { + heap.push(ENC(tmp, i - 1, j)); + visited[i - 1][j] = true; + } + if (i < n + 1 && !visited[i + 1][j]) + { + heap.push(ENC(tmp, i + 1, j)); + visited[i + 1][j] = true; + } + if (j && !visited[i][j - 1]) + { + heap.push(ENC(tmp, i, j - 1)); + visited[i][j - 1] = true; + } + if (j < n + 1 && !visited[i][j + 1]) + { + heap.push(ENC(tmp, i, j + 1)); + visited[i][j + 1] = true; + } + } + + ofstream outfile; + outfile.open("VDD.OUT"); + outfile << (s == 12345 ? 0 : s - 1) << endl; + outfile.close(); + + return 0; +} |