Untitled
unknown
plain_text
a year ago
8.2 kB
2
Indexable
Never
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
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>
#define MAX 0;
using namespace std;
int n, m = 5;
int arr[101][101];
int dR[3] = {-1, -1, -1};
int dC[3] = {-1, 0, 1};
int visited[101][101];
int cost;
int Max;
int lt;
bool flag;
void BackTrack(int i, int j){
if(lt <= 1){
if(i == 0){
Max = max(Max, cost);
flag = true;
}
}
for(int k=0; k<3; k++){
int x = i + dR[k];
int y = j + dC[k];
if(x>=0 && x<n && y>=0 && y<m && visited[x][y] == 0){
visited[x][y] = 1;
if(arr[x][y] == 1)
cost += 1;
else if(arr[x][y] == 2)
lt += 1;
BackTrack(x, y);
if(arr[x][y] == 1)
cost -= 1;
else if(arr[x][y] == 2)
lt -=1;
visited[x][y] = 0;
}
}
}
int main(){
//freopen("vao.txt", "r", stdin);
int t;
cin >> t;
for(int tc=1; tc<=t; tc++){
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin >> arr[i][j];
}
}
for(int i=0; i<n+1; i++){
for(int j=0; j<m; j++){
visited[i][j] = 0;
}
}
for(int i=0; i<m; i++){
arr[n][i] = 2;
}
arr[n][2] = 0;
n+=1;
cost = 0;
lt = 0;
visited[n-1][2] = 1;
Max = MAX;
flag = false;
BackTrack(n-1, 2);
cout << "#" << tc << " ";
if(flag)
cout << Max << endl;
else
cout << "-1" << endl;
}
return 0;
}