Mario Climb
Level 4 Mario Climb Mario cần phải di chuyển từ vị trí có giá trị bằng 2 và ăn vàng ở ô có giá trị bằng 3 0 là nhữngô Mario không thể qua 1 là nhữngô Mario có thể qua 2 là vị trícủa Mario 3 là vị trí Mario cần di chuyển đến Các vị trí này được thể hiện bằng ma trận NxM( 2<=N,M<=50) Mario có thểdi chuyển theo hàng ngang hoặc hàng dọc Hàng ngang mario chỉ nhảy được tối đa 1 bước Hàng dọc mario có thể nhảy được “h” bước Tìm bước nhảy “h” tối thiểu để Mario có thể ăn được vàng Sample Input 3 5 8 1 1 1 1 0 0 0 0 0 0 0 3 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 2 1 1 1 1 1 1 1 5 6 0 1 1 1 0 0 3 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 2 1 1 1 1 1 9 13 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 1 1 Sample output Case #1 2 Case #2 1 Case #3 3 Case #1 2 Case #2 1 Case #3 3 Case #4 1 Case #5 3 Case #6 6 Case #7 3 Case #8 8 Case #9 5 Case #10 7 Case #11 9 Case #12 4 Case #13 11 Case #14 6 Case #15 10 Case #16 10 Case #17 5 Case #18 7 Case #19 5 Case #20 11 Case #21 6 Case #22 22 Case #23 5 Case #24 7 Case #25 9 Case #26 3 Case #27 2 Case #28 7 Case #29 4 Case #30 5 Case #31 9 Case #32 9 Case #33 5 Case #34 7 Case #35 9 Case #36 20 Case #37 5 Case #38 12 Case #39 12 Case #40 8 Case #41 8 Case #42 22 Case #43 11 Case #44 8 Case #45 2 Case #46 10 Case #47 5 Case #48 18 Case #49 49 Case #50 49 Time: 0.56300 s. #include <iostream> #include <time.h> using namespace std; int oo = 2000000000; int T, n, m, mp[51][51], vs[51][51]; int xStart, yStart, xStop, yStop, result; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int dm[4] = {1, 1, 1, 1}; bool inSize(int x, int y){ return x >= 0 && y >= 0 && x < n & y < m; } void resetVs(){ for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++) vs[i][j] = 0; } } void backtrack(int x, int y){ if(vs[xStop][yStop]) return; for(int d = 0; d < 4; d++){ for(int dd = 1; dd <= dm[d]; dd++){ int xx = x + dx[d]*dd; int yy = y + dy[d]*dd; if(inSize(xx, yy) && !vs[xx][yy] && mp[xx][yy] != 0){ vs[xx][yy]++; backtrack(xx, yy); } } } } 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 result = 0; cin >> n >> m; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> mp[i][j]; if(mp[i][j] == 2) xStart = i, yStart = j; else if(mp[i][j] == 3) xStop = i, yStop = j; } } // Solve Problem for(int h = 1; h <= n - 1; h++){ resetVs(); vs[xStart][yStart]++; dm[0] = h, dm[1] = h; backtrack(xStart, yStart); if(vs[xStop][yStop]){ result = h; break; } } // Output cout << "Case #" << tc << "\n" << 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