fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <map>
  4. #include <string>
  5. #include <vector>
  6. #include <set>
  7. #include <climits>
  8. #include <queue>
  9. using namespace std;
  10.  
  11. const int INF = 1000000000;
  12.  
  13. int main() {
  14.     int n, m, n0, m0, n1, m1;
  15.     cin>>n>>m>>n0>>m0>>n1>>m1;
  16. 	vector < vector < pair<int,int> > > g (n*m);
  17.     short **map=(short**)malloc(sizeof(short*)*n);
  18.     for(int i=0;i<n;i++)map[i]=(short*)malloc(sizeof(short)*m);
  19.     for(int i=0;i<n;i++){
  20.         for(int j=0; j<m; j++)
  21.             cin>>map[i][j];
  22.             //fscanf(f,"%hd",&map[i][j]); 
  23.     }
  24.     for(int i=0;i<n;i++){
  25.         for(int j=0; j<m; j++){
  26.             if(i>0){
  27.                 int diff=abs(map[i][j]-map[i-1][j]);
  28.                 g[i+n*j].push_back(make_pair(i-1+n*j,diff));
  29.             }
  30.             if(i<n-1){
  31.                 int diff=abs(map[i][j]-map[i+1][j]);
  32.                 g[i+n*j].push_back(make_pair(i+1+n*j,diff));
  33.             }
  34.             if(j>0){
  35.                 int diff=abs(map[i][j]-map[i][j-1]);
  36.                 g[i+n*j].push_back(make_pair(i+n*(j-1),diff));
  37.             }
  38.             if(j<m-1){
  39.                 int diff=abs(map[i][j]-map[i][j+1]);
  40.                 g[i+n*j].push_back(make_pair(i+n*(j+1),diff));
  41.             }
  42.         }
  43.     }
  44.  
  45. 	int s = n0+m0*n;
  46.     for(int i=0;i<n;i++)free(map[i]);
  47.     free(map);
  48. 	vector<int> d (n*m, INF),  p (n*m);
  49. 	d[s] = 0;
  50.  
  51.     priority_queue < pair<int,int> > q;
  52. 	q.push (make_pair (0, s));
  53. 	while (!q.empty()) {
  54. 		int v = q.top().second,  cur_d = -q.top().first;
  55. 		q.pop();
  56. 		if (cur_d > d[v])  continue;
  57.  
  58. 		for (size_t j=0; j<g[v].size(); ++j) {
  59. 			int to = g[v][j].first,
  60. 				len = g[v][j].second;
  61. 			if (d[v] + len < d[to]) {
  62. 				d[to] = d[v] + len;
  63. 				p[to] = v;
  64. 				q.push (make_pair (-d[to], to));
  65. 			}
  66. 		}
  67. 	}
  68.     cout<<d[n1+m1*n];
  69. }
  70.  
Success #stdin #stdout 0s 4528KB
comments ()
stdin
copy 
2 2 0 0 1 1
0 10
30 20
stdout
copy 
20
https://ideone.com/keraVb
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!