1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
| #include <iostream> #include <bits/stdc++.h> #define LOCAL #define INF 99999999 using namespace std; int intMap[1010][1010] = {} , intValue[1010][1010] = {}; int m , n ;
struct Node{ int x , y , v ; void read( int _x , int _y , int _v){ x = _x ; y = _y ; v = _v ; } bool operator < (const Node &a) const{ return v > a.v ; } }nodNode;
void print_map(){ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= m ; j++){ if(intValue[i][j] == 99999999) cout << 'r' << ' ' ; else cout << intValue[i][j] << ' ' ; } cout << '\n' ; } cout << '\n' ; }
void bfs(){ int x , y , intDirection[4][2] = {-1,0 ,0,1 ,1,0 ,0,-1}; int intDx , intDy ; Node nodTemp ; priority_queue<Node> deqNode ; nodTemp.read(1,1,0); deqNode.push(nodTemp); while(deqNode.size()){ x = deqNode.top().x ; y = deqNode.top().y ; deqNode.pop() ;
for(int i = 0 ; i < 4 ; i++){ intDx = intDirection[i][0] + x ; intDy = intDirection[i][1] + y ;
if(intValue[x][y] + intMap[intDx][intDy] < intValue[intDx][intDy] ){ intValue[intDx][intDy] = intValue[x][y] + intMap[intDx][intDy] ; nodTemp.read(intDx , intDy , intValue[intDx][intDy]); deqNode.push(nodTemp) ; } } } }
int main() { #ifdef LOCAL freopen("in1.txt" , "r" , stdin ); freopen("out.txt" , "w" , stdout) ; #endif ios::sync_with_stdio(false); int intCase ; cin >> intCase ; while(intCase --){ cin >> n >> m ; for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= m ; j++){ cin >> intMap[i][j] ; intValue[i][j] = INF ; } }
for(int i = 1 ; i <= n ; i++){ intValue[i][0] = 0 ; intValue[i][m+1] = 0 ; intMap[i][0] = INF +1 ; intMap[i][m+1] = INF +1 ; } for(int i = 1 ; i <= m ; i++){ intValue[0][i] = 0 ; intValue[n+1][i] = 0 ; intMap[0][i] = INF +1 ; intMap[n+1][i] = INF +1 ; } intValue[1][1] = intMap[1][1] ;
bfs(); cout << intValue[n][m] << '\n' ; } return 0;
}
|