Qua Cầu
Có 1 số cây cầu làm bằng gỗ. Trải qua 1 thời gian,những cây cầu trở nên hư hại và xuất hiện những lỗ thủng trên đó. Được biết những cây cầu đó luôn có độ rộng M = 5(bước đi) và độ dài trong khoảng3
Công việc:
Có 1 người luôn luôn đứng giữa ở 1 phía của cây cầu. Nhiệm vụ của bạn là phải đưa người đó qua được cầu với số đồng xu nhặt được là lớn nhất. Được biết trên cầu có 1 số đồng xu bị đánh rơi và người đó chỉ có thể đi thẳng, đi chéo trái hoặc đi chéo phải. Ngoài ra người đó có mang 1 tấm ván. Nó có thể vá được 1 lỗ thủng trên cầu giúp người đó có thể đi qua được.
Lưu ý : không có nhiều hơn 1 đồng xu tại 1 địa điểm.
Input
Dòng đầu tiên là số lượng trường hợp thử nghiệm.
Dòng thứ 2 chiều dài của cây cầu (N).
N dòng tiếp theo mô tả cây cầu theo ma trận 2 chiều. Trong đó: ‘0’ là có thể đi được, ‘1’ là có đồng xu(có thể đi được)và ‘2’ là lỗ thủng.
Output
In theo định dạng “#test_case” và số đồng xu nhiều nhất có thể khi qua đươc cầu.
Nếu không thể qua cầu in ra -1.
Sample
Input
3
7
1 2 0 1 0
0 0 2 0 1
0 1 0 2 1
1 0 0 0 1
0 0 0 2 2
2 0 1 0 1
0 1 2 2 0
10
2 2 2 2 0
1 2 0 0 2
0 2 0 0 0
2 2 0 2 2
0 2 2 2 0
0 0 0 0 0
1 0 0 0 2
0 0 0 0 0
2 2 0 2 1
0 2 2 2 0
9
0 2 1 1 2
0 2 2 2 2
2 2 2 1 0
0 0 2 0 2
0 2 2 1 0
1 0 2 2 2
2 2 0 2 0
2 2 2 0 2
0 0 2 0 0
Output
#1 6
#2 -1
#3 0
package practice;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/*
* (BFS || DFS) && BackTracking
* nhặt được nhiều tiền xu nhất
* ko đi được tới đích
* đi được tới đích mà ko nhặt được đồng xu nào
* Có 1 cái ván nếu đi ko đúng phải reset lại cái biến ván đó để còn đi tiếp
* Bài này có thể đánh visit or ko đánh visit cũng được
*/
public class QuaCau {
Scanner sc = new Scanner(System.in);
int t, n, van, ans, count;
boolean check;
int map[][];
int visit[][];
int dx[] = { -1, -1, -1 };
int dy[] = { -1, 0, 1 };
void DFS(int startX, int startY) {
visit[startX][startY] = 1;
for (int i = 0; i < 3; i++) {
int x = startX + dx[i];
int y = startY + dy[i];
if (x == -1) {
check = true;
if (count > ans) {
ans = count;
}
return;
}
if (x >= 0 && x < n && y >= 0 && y < 5 && visit[x][y]==0) {
if (map[x][y] == 1) {
visit[x][y]=1;
count++;
DFS(x, y);
visit[x][y]=0;
count–;
}
if (map[x][y] == 0) {
visit[x][y]=1;
DFS(x, y);
visit[x][y]=0;
}
if (map[x][y] == 2) {
if (van == 1) {
visit[x][y]=1;
van = 0;
DFS(x, y);
visit[x][y]=0;
van = 1;
}
// Nếu xét van==0 thì khi nó đi gặp 2 thì van từ 1 về 0 mà đi tiếp phát nữa thì thuật toán của ta tự động né map[][]=2 luôn, chứ có van=0 thì thuật toán vẫn cố tình đi vào map[][]=2
// if(van==0) {
// return;
// }
}
}
}
}
void init() {
check = false;
count = ans = 0;
van = 1;
map = new int[n + 1][5];
visit = new int[n + 1][5];
}
void solution() {
t = sc.nextInt();
for (int tc = 1; tc <= t; tc++) {
n = sc.nextInt();
init();
for (int i = 0; i < n; i++) {
for (int j = 0; j < 5; j++) {
map[i][j] = sc.nextInt();
}
}
DFS(n, 2);
if (check == false) {
System.out.println(“#” + tc + ” -1″);
} else {
System.out.println(“#” + tc + ” ” + ans);
}
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream(“QuaCau.txt”));
QuaCau q = new QuaCau();
q.solution();
}
}
alexishuuuocn 