Qua cau
quoc14
c_cpp
5 months ago
8.4 kB
3
Indexable
Backtrack
Level 4
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
#1 6
#2 -1
#3 0
#4 7
#5 8
#6 8
#7 7
#8 6
#9 4
#10 6
#11 6
#12 5
#13 4
#14 5
#15 3
#16 4
#17 5
#18 5
#19 5
#20 5
#21 4
#22 7
#23 6
#24 7
#25 5
#26 4
#27 5
#28 3
#29 3
#30 5
#31 9
#32 8
#33 7
#34 8
#35 9
#36 8
#37 8
#38 9
#39 6
#40 10
#41 7
#42 -1
#43 6
#44 8
#45 12
#46 1
#47 2
#48 3
#49 2
#50 4
Time: 0.07800 s.
50
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
9
2 2 1 1 1
1 1 2 0 1
0 0 2 0 0
0 2 1 2 0
0 2 1 1 0
2 0 1 1 2
0 2 0 0 2
1 0 2 2 2
1 1 0 0 1
9
1 1 0 1 1
0 0 0 0 0
0 1 0 0 2
2 1 1 1 2
2 2 1 1 0
0 1 0 2 2
1 2 0 1 0
0 1 0 0 2
1 2 1 0 0
9
1 1 1 1 2
0 1 1 1 2
1 1 1 1 2
0 2 2 2 2
1 0 2 1 1
1 2 0 1 0
1 0 1 2 0
1 0 2 0 0
0 1 0 0 1
9
1 2 2 0 1
0 0 0 0 0
2 1 2 1 1
0 2 2 0 0
2 2 1 1 2
1 0 0 1 0
0 2 0 0 1
0 2 1 1 1
2 2 1 0 2
6
0 2 2 1 0
2 0 1 0 0
1 2 1 2 2
2 2 0 1 0
0 1 1 2 1
0 1 2 0 1
6
0 1 1 2 1
0 2 0 2 2
0 0 2 1 2
0 2 0 1 1
0 1 0 1 0
1 0 0 2 2
6
0 0 0 1 0
0 2 1 2 0
1 2 0 1 2
2 2 1 1 2
1 2 2 1 1
1 2 1 1 2
6
1 1 0 2 1
2 2 1 2 2
1 1 2 1 2
0 1 2 0 0
0 1 0 0 0
0 1 2 2 2
6
2 1 2 1 1
2 2 2 1 1
1 2 0 1 1
0 1 2 1 0
2 0 1 0 0
0 0 2 0 1
7
2 2 0 0 0
0 2 0 0 1
2 2 0 2 2
2 1 2 2 0
1 0 2 1 1
0 1 1 0 2
0 0 1 0 2
7
2 0 0 1 0
2 1 1 1 1
0 0 0 2 2
0 2 1 2 1
1 0 0 1 0
0 2 2 2 0
1 1 0 1 2
7
2 2 0 2 2
0 1 0 1 0
1 1 0 2 0
2 2 2 1 2
1 0 2 2 1
0 0 0 0 2
0 0 2 2 1
7
0 0 0 2 2
1 2 2 1 1
2 0 2 0 2
1 1 2 0 0
0 0 2 2 0
2 2 1 0 2
1 1 1 2 1
7
1 0 2 2 0
1 0 0 2 1
1 0 2 2 2
2 0 1 1 0
0 2 0 1 2
0 0 0 1 2
1 0 0 0 0
7
1 0 1 1 2
2 1 0 0 0
0 0 2 1 1
2 2 0 0 0
1 0 2 2 2
0 1 0 1 0
0 2 1 0 1
7
2 0 0 2 1
1 1 0 0 1
1 1 0 2 2
2 0 0 2 1
0 2 2 1 0
2 0 2 0 1
0 1 1 2 2
7
2 1 0 1 2
0 0 0 1 0
2 1 2 0 2
2 2 0 1 2
2 0 0 0 2
2 1 0 0 0
2 1 2 1 2
8
0 0 2 0 2
0 0 0 2 2
1 0 1 1 0
2 2 2 1 2
0 2 0 2 1
1 0 0 2 0
2 0 0 2 1
0 2 0 0 1
8
1 0 0 2 1
0 1 0 1 0
2 0 1 2 0
1 2 2 1 0
0 0 2 2 2
0 2 1 2 0
0 0 0 1 2
2 2 2 1 1
8
2 2 2 0 2
2 0 2 1 2
2 1 0 0 0
1 1 1 0 0
1 2 0 1 2
2 0 2 2 1
2 1 1 0 1
0 1 0 1 0
8
1 1 2 0 0
1 2 0 2 1
2 1 1 0 0
1 2 0 0 1
1 2 0 0 2
1 2 2 2 2
1 0 2 1 1
2 0 1 1 0
8
2 2 1 1 2
0 1 2 0 0
1 2 2 2 2
2 2 2 2 2
2 2 0 0 1
0 2 2 1 0
0 1 2 1 1
2 1 0 0 1
5
1 2 2 2 0
1 2 0 0 1
2 2 1 1 0
1 0 2 1 0
2 1 0 1 2
5
0 1 0 2 1
1 1 1 0 2
1 1 2 2 0
0 2 1 2 1
0 2 2 1 0
5
0 1 1 1 0
0 0 0 0 2
0 2 2 2 1
0 1 1 1 1
0 1 2 2 1
5
0 2 0 0 2
0 0 0 2 1
0 1 2 0 2
2 2 2 1 2
0 1 1 2 2
5
2 2 1 2 0
1 2 1 2 0
2 1 1 2 0
0 2 1 1 0
1 2 1 0 0
10
1 2 1 0 0
2 1 1 2 1
0 0 2 1 0
0 0 2 1 0
1 2 0 2 0
2 1 2 2 2
0 1 1 1 0
0 1 1 1 1
1 2 2 1 2
0 2 1 0 0
10
1 0 2 2 0
1 0 2 0 0
1 2 0 0 1
1 1 1 0 2
1 1 2 2 0
0 0 0 0 2
2 2 1 1 0
0 0 0 2 1
0 1 0 0 0
2 1 0 2 1
10
2 1 2 0 0
1 2 0 0 2
2 0 1 2 0
2 0 2 2 2
1 1 0 1 1
1 2 1 1 0
1 1 2 2 1
1 0 1 2 1
1 1 1 2 1
1 0 0 2 1
10
0 0 1 0 0
1 0 2 2 1
2 1 1 2 1
1 1 1 0 1
0 0 1 1 2
2 2 2 1 0
0 2 1 0 0
2 2 1 0 2
2 2 2 0 2
1 1 2 1 0
10
0 0 0 1 0
0 2 2 1 0
2 1 1 1 1
1 0 1 2 0
1 1 0 1 0
0 2 2 1 2
0 1 0 2 2
0 1 1 2 2
1 1 0 1 1
2 0 2 1 1
11
0 0 0 2 1
1 1 0 0 2
2 0 2 2 0
0 1 1 1 2
2 0 1 0 2
0 0 0 1 1
0 1 1 1 0
0 2 2 1 2
0 2 2 0 2
2 1 1 0 0
0 2 1 0 0
11
2 0 1 2 0
1 0 0 0 1
0 1 2 2 2
2 1 1 0 2
2 0 2 2 0
2 2 1 0 1
1 1 0 0 2
0 1 2 0 1
2 0 1 2 1
2 2 0 0 0
2 0 1 0 0
11
2 1 1 0 2
1 1 0 2 2
2 0 2 1 1
2 1 2 1 0
2 2 2 2 1
1 2 1 1 1
0 0 1 2 2
0 0 1 2 2
0 0 2 2 0
0 1 0 2 2
2 1 1 1 1
11
2 0 0 2 0
0 1 0 0 0
0 2 1 0 0
2 0 0 0 2
0 0 0 2 2
1 1 0 2 1
1 0 2 0 1
2 0 1 0 2
1 2 1 2 0
0 0 0 0 1
2 1 0 2 2
11
1 1 1 1 0
1 1 0 0 0
2 0 1 2 2
1 2 0 1 2
2 0 0 1 2
2 1 1 2 0
1 0 1 2 0
2 2 2 1 2
0 0 2 1 0
1 0 2 2 0
2 2 0 1 0
12
0 2 1 0 1
1 1 0 2 0
2 1 0 1 0
2 2 0 1 2
0 2 0 0 2
1 2 2 1 1
0 1 0 0 0
1 2 2 0 1
0 0 1 1 0
2 0 2 0 0
1 2 2 0 2
0 0 1 1 0
12
1 2 2 0 0
0 2 2 1 2
1 1 2 1 2
2 0 0 2 2
2 1 0 0 0
1 2 2 1 2
1 1 0 1 0
1 2 2 2 0
0 1 1 2 1
1 2 2 2 0
2 2 2 2 2
0 2 2 2 1
12
1 1 2 0 0
2 0 0 1 1
2 1 2 0 1
1 0 2 0 0
2 0 1 2 0
2 2 0 0 1
0 1 1 2 1
1 2 0 0 0
0 2 1 2 0
0 2 1 2 1
2 0 0 0 1
1 0 2 0 1
12
2 2 0 0 0
2 0 0 0 1
1 0 0 0 0
1 0 1 1 0
1 1 1 1 2
0 1 2 2 2
1 0 2 0 1
0 1 2 0 1
2 0 0 0 2
0 1 2 2 1
0 2 2 0 1
0 1 0 0 0
12
2 1 1 1 2
2 1 0 0 1
1 1 1 1 0
2 1 0 0 0
0 1 2 0 0
1 1 0 1 2
2 1 2 0 2
2 1 1 1 0
1 1 1 2 1
2 1 1 2 1
2 1 2 2 1
0 1 0 2 0
4
1 2 2 2 2
0 2 2 2 0
0 2 0 2 1
0 2 0 2 0
4
2 0 0 0 1
2 2 2 2 2
1 0 2 0 2
2 0 2 1 2
4
0 2 2 1 1
0 2 1 0 1
1 0 0 1 2
1 0 2 0 1
4
2 1 0 0 0
0 2 2 2 0
1 0 2 0 1
1 2 2 1 1
4
0 2 0 1 0
1 1 1 2 2
1 1 2 1 1
2 2 1 1 1
#include <iostream>
#include <time.h>
using namespace std;
int oo = 2000000000;
int T, n, result, maxx, m;
int mp[12][12];
// up down left right
int dx[3] = {-1, -1, -1};
int dy[3] = {-1, 0, 1};
bool inSize(int x, int y){
return x >= 0 && y >= 0 && x < n && y < 5;
}
void backtrack(int index, int x, int y, int coin, bool hasBridge){
if(index == 0){
if(coin > result) result = coin;
return;
}
for(int d = 0; d < 3; d++){
int xx = x + dx[d];
int yy = y + dy[d];
if(inSize(xx, yy)){
if(mp[xx][yy] < 2) backtrack(index - 1, xx, yy, coin + mp[xx][yy], hasBridge);
else if(mp[xx][yy] == 2 && hasBridge) backtrack(index - 1, xx, yy, coin, false);
}
}
}
int main(){
freopen("input.txt", "r", stdin);
// Calc clock
clock_t time_start, time_end;
time_start = clock();
cin >> T;
for(int tc = 1; tc <= T; tc++){
// Initial && Input
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < 5; j++) {
cin >> mp[i][j];
}
}
result = -oo;
// Solve Problem
backtrack(n, n, 2, 0, true);
// Output
cout << "#" << tc << " " << (result == -oo ? -1 : result) << endl;
}
// Calc Time
time_end = clock();
cout.setf(ios::fixed);
cout.precision(5);
cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
return 0;
}Leave a Comment