Untitled
unknown
plain_text
2 years ago
10 kB
10
Indexable
Thong tri khu vuc
Cho ma trận NxN (5 ≤ N ≤ 100) chứa các phần tử có giá trị 0 – 5 mô tả lãnh thổ 6
vương quốc. Yêu cầu sáp nhập các vùng số 0 về các lãnh thổ khác sao cho vùng đồng
nhất có diện tích lớn nhất (các vùng được chuyển đổi trước không được tính vào diện
tích để quyết định các vùng chuyển đổi sau), sau đó trả về số lượng vùng còn lại sau
khi sáp nhập.
5 5 1 4 4
4 0 2 4 2
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
Thông thường, chúng ta có thể thấy rõ rằng có hai ô 5, hai ô 4, một ô 3 và hai ô 2 gian hàng xung quanh ba ô 0 này. Tuy nhiên, vì ô 5 cũng kết nối với ô khác cùng loại (ô 5, tại vị trí [1,1] và [4,1] với màu xanh lam), diện tích sẽ trở lên tốt hơn, vì vậy chúng tôi coi tần suất của ô 5 là 4. Trong trường hợp có nhiều hơn một loại ô có cùng tần suất cao nhất, chúng tôi sẽ chọn ô có giá trị cao hơn.
5 5 1 4 4
4 5 2 4 2
5 5 5 2 0
5 4 3 0 1
1 3 3 2 1
Tiếp tục với ô 0 tiếp theo ta có ma trận bên dưới
5 5 1 4 4
4 5 2 4 2
5 5 5 2 2
5 4 3 3 1
1 3 3 2 1
Tất cả các Ô cùng loại và cạnh nhau (trên / dưới/ trái / phải) kết nối thành một khu vực.
5 5 1 4 4
4 5 2 4 2
5 5 5 2 2
5 4 3 3 1
1 3 3 2 1
Ở ví dụ này chúng ta có 11 vùng
.
[Input]
- Số lượng test case T (T <= 50)
- Kích thước ma trận N (5 <= N <= 100)
- Chi tiết ma trận được cho trong N hàng tiếp theo, Giá trị của mỗi ô có giá trị C (0 <= C <= 5)
5
5
5 5 1 4 4
4 0 2 4 2
5 0 0 2 0
5 4 3 0 1
1 3 3 2 1
7
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
5 0 5 0 5 0 5
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
10
1 3 5 1 4 0 0 4 2 1
1 1 2 1 1 0 5 0 2 1
5 0 2 0 4 4 4 0 1 1
0 2 2 4 0 5 4 2 1 3
1 1 2 2 2 3 3 2 1 1
5 1 1 2 0 3 3 2 2 1
3 1 1 1 0 0 1 2 2 5
3 1 4 1 2 0 4 0 0 5
4 0 3 3 1 3 3 0 0 1
5 0 3 1 4 3 3 1 2 3
...
[Output]
- Xuất ra số lượng vùng sau khi đổi các vùng số 0
Case #1
11
Case #2
1
Case #3
31
...
[Constraint]
- Tất cả các ô số 0 cạnh nhau (trên/dưới/trái/phải) được tính là 1 khu vực.
- Chỉ có 6 loại ô từ : 0 - 5, ô sô 0 cần được thay đổi thành các số khác từ (1-5)
- Chúng tôi đảm bảo sẽ không có trường hợp nào trong đó tất cả các ô bằng không
- Tất cả các loại ô giống nhau nằm xung quanh nhau được coi là một khu vực.
- Time limit : 3s for 50 TC ( C, C++ 3000 msec, Java 6000 msec)
#include<iostream>
using namespace std;
int n, maxx;
int arr[100][100], visit[100][100], replace[100][100];
int cnt[6];
int front, rear, frontZ, rearZ;
int queueX[1000000];
int queueY[1000000];
int queueXzone[1000000];
int queueYzone[1000000];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};
int Answer;
void reset() {
for (int i = 0; i < 6; i++) {
cnt[i] = 0;
}
}
void push(int x, int y) {
rear++;
queueX[rear]=x;
queueY[rear]=y;
}
void pop(int &x, int &y) {
front++;
x=queueX[front];
y=queueY[front];
}
void replacee() {
maxx = 0;
int index;
for (int i = 5; i >= 1; i--) {
if (cnt[i] > maxx) {
maxx = cnt[i];
index = i;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visit[i][j] == 1) {
visit[i][j] = 0;
}
}
}
while (frontZ < rearZ) {
int x = queueXzone[frontZ];
int y = queueYzone[frontZ];
frontZ++;
arr[x][y] = index;
visit[x][y] = -1;
}
}
void spread(int x, int y) {
for (int j = 0; j < 4; j++) {
int _xx = x + dx[j];
int _yy = y + dy[j];
if (_xx >= 0 && _xx < n && _yy >= 0 && _yy < n) {
if (arr[_xx][_yy] == arr[x][y] && visit[_xx][_yy] == 0) {
cnt[arr[x][y]]++;
visit[_xx][_yy] = 1;
spread(_xx, _yy);
}
}
}
}
/*void find() {
while (front < rear) {
int x = queueX[front];
int y = queueY[front];
front++;
for (int i = 0; i < 4; i++) {
int _x = x + dx[i];
int _y = y + dy[i];
if (_x >= 0 && _x < n && _y >= 0 && _y < n) {
if (arr[_x][_y] == 0 && visit[_x][_y] == 0) {
visit[_x][_y] = 1;
queueX[rear] = _x;
queueY[rear] = _y;
rear++;
queueXzone[rearZ] = _x;
queueYzone[rearZ] = _y;
rearZ++;
} else if (arr[_x][_y] != 0 && visit[_x][_y] == 0) {
cnt[arr[_x][_y]]++;
visit[_x][_y] = 1;
spread(_x, _y);
}
}
}
}
replacee();
}*/
void find_replace() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == 0 && visit[i][j] == 0) {
reset();
visit[i][j] = 1;
front = rear = 0;
frontZ = rearZ = 0;
queueX[front] = i;
queueY[front] = j;
rear++;
queueXzone[frontZ] = i;
queueYzone[frontZ] = j;
rearZ++;
while (front < rear) {
int x = queueX[front];
int y = queueY[front];
front++;
for (int i = 0; i < 4; i++) {
int _x = x + dx[i];
int _y = y + dy[i];
if (_x >= 0 && _x < n && _y >= 0 && _y < n) {
if (arr[_x][_y] == 0 && visit[_x][_y] == 0) {
visit[_x][_y] = 1;
queueX[rear] = _x;
queueY[rear] = _y;
rear++;
queueXzone[rearZ] = _x;
queueYzone[rearZ] = _y;
rearZ++;
} else if (arr[_x][_y] != 0 && visit[_x][_y] == 0) {
cnt[arr[_x][_y]]++;
visit[_x][_y] = 1;
spread(_x, _y);
}
}
}
}
replacee();
}
}
}
}
void cnt_zone() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visit[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visit[i][j] == 0) {
visit[i][j] = 1;
front = rear = 0;
queueX[front] = i;
queueY[front] = j;
rear++;
while (front < rear) {
int x = queueX[front];
int y = queueY[front];
front++;
for (int i = 0; i < 4; i++) {
int _x = x + dx[i];
int _y = y + dy[i];
if (_x >= 0 && _x < n && _y >= 0 && _y < n) {
if (arr[_x][_y] == arr[x][y] && visit[_x][_y] == 0) {
visit[_x][_y] = 1;
queueX[rear] = _x;
queueY[rear] = _y;
rear++;
}
}
}
}
Answer++;
}
}
}
}
int main(int argc, char** argv)
{
int test_case;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for(test_case = 1; test_case <= T; ++test_case)
{
Answer = 0;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visit[i][j] = 0;
}
}
reset();
find_replace();
cnt_zone();
// Print the answer to standard output(screen).
cout << "Case #" << test_case << endl << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}
/*#include<iostream>
using namespace std;
int N;
int map[105][105];
int temp[105][105];
int visit[105][105];
int cnt[6];
int dR[4] = {0, -1, 0, 1};
int dC[4] = {-1, 0, 1, 0};
struct COOR {
int r, c;
} Queue[10005], Q[10005];
int front, rear;
void init() {
front = rear = -1;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
visit[i][j] = 0;
for (int i = 1; i < 6; i++)
cnt[i] = 0;
}
void push(int r, int c) {
rear++;
Queue[rear].r = r;
Queue[rear].c = c;
}
COOR pop() {
return Queue[++front];
}
bool isEmpty() {
return front == rear;
}
void BFS1(int r, int c) {
int front1 = -1, rear1 = -1;
visit[r][c] = 1;
rear1++;
Q[rear1].r = r; Q[rear1].c = c;
cnt[map[r][c]]++;
while (front1 != rear1) {
front1++;
int topR = Q[front1].r; int topC = Q[front1].c;
for (int i = 0; i < 4; i++) {
int nR = topR + dR[i];
int nC = topC + dC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < N && !visit[nR][nC]) {
if (map[nR][nC] == map[topR][topC]) {
visit[nR][nC] = 1;
rear1++;
Q[rear1].r = nR; Q[rear1].c = nC;
cnt[map[nR][nC]]++;
}
}
}
}
}
void BFS(int r, int c) {
init();
visit[r][c] = 1;
push(r, c);
while (!isEmpty()) {
COOR coor = pop();
for (int i = 0; i < 4; i++) {
int nR = coor.r + dR[i];
int nC = coor.c + dC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < N && !visit[nR][nC]) {
if (temp[nR][nC] == 0) {
visit[nR][nC] = 1;
push(nR, nC);
} else {
BFS1(nR, nC);
}
}
}
}
}
void BFS2(int r, int c) {
visit[r][c] = 1;
push(r, c);
while (!isEmpty()) {
COOR coor = pop();
for (int i = 0; i < 4; i++) {
int nR = coor.r + dR[i];
int nC = coor.c + dC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < N && !visit[nR][nC]) {
if (temp[nR][nC] == temp[coor.r][coor.c]) {
visit[nR][nC] = 1;
push(nR, nC);
}
}
}
}
}
int findMax() {
int m = -1;
int idx = 0;
for (int i = 1; i < 6; i++) {
if (cnt[i] >= m) {
m = cnt[i];
idx = i;
}
}
return idx;
}
int main() {
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for (int test_case = 1; test_case <= T; ++test_case) {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> map[i][j];
temp[i][j] = map[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (temp[i][j] == 0) {
BFS(i, j);
int val = findMax();
for (int i = 0; i <= rear; i++) {
temp[Queue[i].r][Queue[i].c] = val;
}
}
}
}
init();
int ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j]) {
BFS2(i, j);
ans++;
}
}
}
cout << "Case #" << test_case << endl << ans << endl;
}
return 0;
}*/
Editor is loading...