Moutain walking
Level 4 Mountain Walking Cho một bản đồ kích thước NxN (2 <= N <= 100), mỗi ô mang giá trị là độ cao của ô đó (0 <= độ cao <= 110). Bác John và bò Bessie đang ở ô trên trái (dòng 1, cột 1) và muốn đi đến cabin (dòng N, cột N). Họ có thể đi sang phải, trái, lên trên và xuống dưới nhưng không thể đi theo đường chéo. Hãy giúp bác John và bò Bessie tìm đường đi sao cho chênh lệch giữa điểm cao nhất và thấp nhất trên đường đi là nhỏ nhất. Input Dòng 1: Số test case Dòng 2: N N dòng tiếp theo chứa N số nguyên, mỗi số cho biết cao độ của một ô. Output In ra #test case và một số nguyên là chênh lệch độ cao nhỏ nhất. Sample Input 5 5 1 1 3 6 8 1 2 2 5 5 4 4 0 3 3 8 0 2 3 4 4 3 0 2 1 5 99 85 38 22 55 89 28 33 3 65 99 20 14 67 90 36 27 28 77 31 50 45 12 9 14 2 92 83 19 91 5 61 49 32 34 28 100 65 0 10 89 34 99 40 86 4 10 97 49 21 30 95 33 79 51 65 2 17 60 94 27 Output #1 2 #2 85 #3 9 #4 50 #5 43 #1 2 #2 85 #3 81 #4 61 #5 63 #6 61 #7 63 #8 68 #9 66 #10 65 #11 66 #12 59 #13 68 #14 64 #15 61 #16 71 #17 84 #18 73 #19 64 #20 49 #21 62 #22 61 #23 58 #24 75 #25 61 #26 100 #27 84 #28 65 #29 70 #30 61 #31 63 #32 66 #33 64 #34 64 #35 61 #36 64 #37 63 #38 71 #39 96 #40 61 #41 69 #42 66 #43 70 #44 71 #45 63 #46 84 #47 58 #48 58 #49 74 #50 72 Time: 1.08600 s. #include <iostream> #include <time.h> using namespace std; int oo = 2000000000; int T, n, mp[101][101]; int result; int vs[101][101]; int minV, maxV; int q[10001][2], head, tail; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int Min(int a, int b){return a > b ? b : a;} int Max(int a, int b){return a < b ? b : a;} bool checkBfs(int low, int high){ if(mp[1][1] > high || mp[1][1] < low) return false; if(mp[n][n] > high || mp[n][n] < low) return false; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++) vs[i][j] = 0; } head = 0, tail = 0; q[tail][0] = 1; q[tail++][1] = 1; while(head != tail){ int x = q[head][0]; int y = q[head][1]; head++; if(x == n && y == n) return true; for(int d = 0; d < 4; d++){ int xx = x + dx[d]; int yy = y + dy[d]; if(xx >= 1 && yy >= 1 && xx <= n && yy <= n && vs[xx][yy] == 0){ if(mp[xx][yy] <= high && mp[xx][yy] >= low){ vs[xx][yy]++; q[tail][0] = xx; q[tail++][1] = yy; } } } } return false; } void Search(){ for(int len = 0; len <= maxV - minV + 1; len++){ bool isStop = false; for(int start = minV; start <= maxV - len; start++){ if(checkBfs(start, start + len)){ isStop = true; result = len; break; } } if(isStop) break; } } int main(){ // read input freopen("input.txt", "r", stdin); //calc time clock_t tStart, tStop; tStart = clock(); cin >> T; for(int tc = 1; tc <= T; tc++){ // input and initial minV = oo, maxV = -oo; cin >> n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cin >> mp[i][j]; vs[i][j] = 0; minV = Min(minV, mp[i][j]); maxV = Max(maxV, mp[i][j]); } } result = oo; // solve problem Search(); // output cout << "#" << tc << " " << result << endl; } //calc time tStop = clock(); cout.setf(ios::fixed); cout.precision(5); cout << "Time: " << double(tStop - tStart) / CLOCKS_PER_SEC << " s." << endl; return 0; }
Leave a Comment