Qua_cau
duyvan
plain_text
20 days ago
3.1 kB
4
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 ============================= #include <iostream> using namespace std; int dx[] = {-1,-1,-1}; int dy[] = {-1,0,1}; int N, xu; int a[15][6], visit[15][6]; void nhap(){ cin >> N; for(int i=0; i<N; i++){ for(int j=0; j<5; j++){ cin >> a[i][j]; visit[i][j] = 0; } } } void backtrack(int r, int c, int coin, int hp){ for(int i=0; i<3; i++){ int nx = r + dx[i]; int ny = c + dy[i]; if(nx>=0 && nx<N && ny>=0 && ny<5){ if(a[nx][ny] == 0){ backtrack(nx,ny,coin,hp); } if(a[nx][ny] == 1){ backtrack(nx,ny,coin+1,hp); } if(a[nx][ny] == 2 && hp>0){ backtrack(nx,ny,coin,hp-1); } } } if(r==0){ if(xu<coin) xu = coin; return; } } int main(){ freopen("INP.txt","r",stdin); int T; cin >> T; for(int tc=1; tc<=T; tc++){ nhap(); xu = -1; for(int i=1; i<4; i++){ if(a[N-1][i] == 0){ backtrack(N-1, i, 0, 1); } if(a[N-1][i] == 1){ backtrack(N-1, i, 1, 1); } if(a[N-1][i] == 2){ backtrack(N-1, i, 0, 0); } } cout << '#' << tc << " " << xu << endl; } return 0; }
Leave a Comment