Untitled
unknown
plain_text
2 years ago
2.8 kB
6
Indexable
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<n<=12 font="" <="" đi).="" (bước="" style="margin: 0px; padding: 0px;"></n<=12> 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 Code: #include<iostream> using namespace std; int a[20][5]; int X[3] = { 1,-1, 0}; int Y[3] = {-1,-1, -1}; int ans; int n; void Try(int row, int col, int plank, int sum){ if(row ==0){ if (ans < sum )ans = sum; return; } for(int h =0; h<3; h++){ int r = row +Y[h]; int c = col +X[h]; if(r >=0 && r<n && c>=0 && c<5){ if ( a[r][c] <2 ){ Try(r, c, plank, sum + a[r][c]); } else{ if(plank){ Try(r,c,0,sum); } } } } } int main(){ freopen("text.txt", "r", stdin); int test; cin >> test; //freopen("text.txt", "r", stdin); for(int tc= 1; tc <= test; tc++){ cin >> n; for(int i=0; i < n; i++){ for(int j= 0; j < 5; j++){ cin >> a[i][j]; } } ans =-1; Try(n, 2, 1, 0); cout << "#" << tc << " " << ans << endl; } return 0; }
Editor is loading...