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; }