# Untitled

unknown
plain_text
22 days ago
8.0 kB
2
Indexable
Never
```import java.util.Scanner;

class Solution {
static int n, m, SR, SC, l, h, e, max, sum, t;
static int[][] map = new int[15][15];
static int[][] fire = new int[15][15];
static boolean[][] lake = new boolean[15][15];
static boolean[][] exit = new boolean[15][15];

static boolean[][] visit = new boolean[15][15];
static int[] dr = { -1, 0, 1, 0 };
static int[] dc = { 0, 1, 0, -1 };

static Queue Q1 = new Queue();
static Queue Q2 = new Queue();

// bfs
static void fire() {
int parentR, parentC;
while (!Q1.isEmpty()) {
parentR = Q1.pop();
parentC = Q2.pop();
for (int i = 0; i < 4; i++) {
int nr = parentR + dr[i];
int nc = parentC + dc[i];
if (nr >= 0 && nc >= 0 && nr < n && nc < m && fire[nr][nc] == 10000
&& !lake[nr][nc]) {
Q1.push(nr);
Q2.push(nc);
fire[nr][nc] = fire[parentR][parentC] + 1;
}
}
}
}

static void Try(int r, int c, int time, int sum) {
if (exit[r][c]) {
max = max > sum ? max : sum;
}

for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];

if (nr >= 0 && nc >= 0 && nr < n && nc < m && !visit[nr][nc]) {
int nextTime = lake[nr][nc] ? time + 2 : time + 1;
if (nextTime < fire[nr][nc]) {
visit[nr][nc] = true;
Try(nr, nc, nextTime, sum + map[nr][nc]);
visit[nr][nc] = false;
}
}
}

}

static void reset() {
for (int i = 0; i < 15; i++) {
for (int j = 0; j < 15; j++) {
map[i][j] = 0;
fire[i][j] = 10000;
visit[i][j] = false;
lake[i][j] = false;
exit[i][j] = false;

}
}
Q1.reset();
Q2.reset();
}

public static void main(String args[]) throws Exception {
//System.setIn(new FileInputStream("input.txt"));

Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();

for (int test_case = 1; test_case <= T; test_case++) {
reset();
n = sc.nextInt();
m = sc.nextInt();
SR = sc.nextInt() - 1;
SC = sc.nextInt() - 1;

l = sc.nextInt();
for (int i = 0; i < l; i++) {
int x = sc.nextInt() - 1;
int y = sc.nextInt() - 1;
fire[x][y] = 0;
Q1.push(x);
Q2.push(y);
}

h = sc.nextInt();

for (int i = 0; i < h; i++) {
int x = sc.nextInt() - 1;
int y = sc.nextInt() - 1;
lake[x][y] = true;
}

e = sc.nextInt();

for (int i = 0; i < e; i++) {
int x = sc.nextInt() - 1;
int y = sc.nextInt() - 1;
exit[x][y] = true;
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}

max = -1;
sum = 0;
t = 1;
visit[SR][SC] = true;
fire();
Try(SR, SC, 0, map[SR][SC]);
System.out.println("Case #" + test_case);
System.out.println(max);

}
}

static class Queue {

static int MAX_Q = 1000;
static int[] A = new int[MAX_Q];
public static int front;
public static int rear;

public Queue() {
front = 0;
rear = -1;
}

public Boolean isEmpty() {
if (front > rear)
return true;
return false;
};

public Boolean is_full() {
if (rear == MAX_Q - 1)
return true;
return false;
};

public void push(int c) {
if (is_full()) {
System.out.println("queue is full");

}
rear++;
A[rear] = c;
};

public int pop() {
if (isEmpty()) {
System.out.println("queue is empty");

} else {
front++;

}
return A[front - 1];

};

public int peek() {

return A[front];
};

public void reset() {
front = 0;
rear = -1;
return;
}

}
}
-------------------------------------------------------------------------------------
Hugo đào vàng trả nợ

Sau khi ăn trộm được mật của chị ong nâu và say sưa thưởng thức mật ngọt say đắm thì bất ngờ Hugo bị chị ong nâu phát hiện. Mặc dù đã thành khẩn nhận lỗi và xin lỗi chị ong nâu nhưng do đã đánh chén gần hết số mật đã ăn chộm nên chị ong nâu vẫn bắt Hugo phải bồi thường số mật đó. Hugo thì làm sao có thể kiếm mật được vì vậy Hugo phải đi đào vàng kiếm tiền để có tiền mua mật trả cho chị ong nâu.

Một cách tình cờ Hugo có được bản đồ của một khu vực chứa vàng, bản đồ được vẽ dựa trên một ma trận NxN. Trong ma trận có các điểm chứa vàng có thể khai thác (Tối đa 4 điểm). Hàng ngày Hugo sẽ phải đi tới mỏ vàng để khai thác và cuối ngày sẽ phải mang vàng trở về. Để tiết kiệm chi phí và thời gian, Hugo quyết định cắm trại trên gần mỏ vàng để tiện khai thác vàng. Hugo không thể di chuyển qua khu vực đá và không thể cắm trại trên đá, đồng thời Hugo cũng không thể cắm trại tại khu vực mỏ vàng, thời gian để Hugo di chuyển qua mỗi ô là 1 giờ.

Hãy giúp Hugo tìm địa điểm tối ưu để đi khai thác tất cả các mỏ vàng nhanh nhất.

Xem xét ma trận mỏ vàng 5x5 bên dưới:

X

1

2

X: Vị trí

Gold

Đá

Đường

Có 2 mỏ vàng, nếu Hugo cắm trại tại vị trí X, Hugo sẽ mất 4 giờ để đi tới mỏ vàng thứ 1, và 6 giờ để đi tới mỏ vàng thứ 2, vì vậy thời gian nhỏ nhất để Hugo đi khai thác vàng là 6 giờ, thời gian lớn nhất để đi khai thác của tất cả các mỏ vàng.

Xem xét ví dụ khác:

X

X

X

Thời gian là 4

Thời gian là 1

Thời gian là 3

Thời gian tối ưu với ma trận mỏ vàng trên là 1.

Một mỏ vàng được coi là không thể tiếp cận khi không thể đặt 1 vị trí cắm trại nào để đi khai thác vàng.

[Input]

Số trường hợp thử nghiệp T (T ≤ 50)

Mỗi TC :

- Dòng đầu tiên chứa kích thước ma trận N (N ≤ 20) và số mỏ vàng G (2 ≤ G ≤ 4)

- G dòng tiếp theo đưa ra vị trí R (hàng) & C (cột) của mỏ vàng (Chỉ số bắt đầu từ 1)

- N dòng tiếp theo là thông tin ma trận: 1 là có đường đi và vị trí mỏ vàng, 0 là đá (không thể đi qua).

[Output]

Dòng đầu tiên: In ra chi phí nhỏ nhất để đi từ trại tới điểm đào vàng xa nhất. Nếu không thể tiếp cận tất cả các mỏ vàng, in ra -1

Nếu có bất kỳ mỏ vàng nào không thể tiếp cận, bạn nên in ra vị trí của chúng trên mỗi dòng theo thứ tự đã nhập vào. Bạn nên đặt vị trí trại sao cho Hugo có thể tiếp cận được nhiều mỏ vàng nhất có thể. Ưu tiên các mỏ vàng xuất hiện trước theo thứ tự nhập.

Case #1

1

Case #2

2

Case #3

2

Case #11

1

4 3

4 5

6 10

Case #48

-1

Case #49

11

[Constraints]

- Hugo có thể đi theo 4 hướng (trên/dưới/trái/phải)

- Hugo không thể cắm trại ở vị trí mỏ vàng hoặc

- Hugo có thể đi qua mỏ vàng để đến mỏ vàng

- Hugo cần đặt vị trí trại để tối đa hóa số lượng mỏ vàng có thể khai thác```