fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<queue>
  4. #include<vector>
  5. #include<string.h>
  6. #define infinity 9999999
  7. #define max 1100
  8. #define temp 0
  9. #define perm 1
  10. using namespace std;
  11. char crnt[max][max];
  12. int dist[max][max];
  13. int status[max][max];
  14. struct st
  15. {
  16. 	int u;
  17. 	int v;
  18. 	int w;
  19. };
  20. struct compare
  21. {
  22. 	bool operator()(const st& s1,const st& s2)
  23. 	{
  24. 		return s1.w>s2.w;
  25. 	}
  26. };
  27. priority_queue<st,vector<st>,compare > pq;
  28. int adj[][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
  29. int r,c,rs,cs,rd,cd,t;
  30. int is_safe(int x,int y)
  31. {
  32. 	if(x<1||y<1||x>r||y>c)
  33. 	   return 0;
  34. 	return 1;
  35. }
  36. void reset_dist()
  37. {
  38. 	for(int i=1;i<=r;i++)
  39. 	{
  40. 		for(int j=1;j<=c;j++)
  41. 		{
  42. 			dist[i][j]=999999;
  43. 		}
  44. 	}
  45. }
  46. int dijkstra()
  47. {
  48. 	reset_dist();
  49. 	dist[rs][cs]=0;int d;
  50. 	st s1={rs,cs,dist[rs][cs]};
  51. 	pq.push(s1);
  52. 	while(!pq.empty())
  53. 	{
  54. 		st s1=pq.top();
  55. 		pq.pop();
  56. 		status[s1.u][s1.v]=1;
  57. 		for(int k=0;k<8;k++)
  58. 		{
  59. 			int xc=s1.u+adj[k][0];
  60. 			int yc=s1.v+adj[k][1];
  61. 			if(is_safe(xc,yc))
  62. 			{
  63. 				if(k==crnt[s1.u][s1.v]-'0')
  64. 				    d=dist[s1.u][s1.v];
  65. 				else
  66. 				    d=dist[s1.u][s1.v]+1;
  67. 				if(dist[xc][yc]>d)
  68. 				{
  69. 					dist[xc][yc]=d;
  70. 					if(status[xc][yc]==0)
  71. 					{
  72. 						st s1={xc,yc,dist[xc][yc]};
  73. 						pq.push(s1);
  74. 					}
  75. 				}
  76.  
  77. 			}
  78. 		}
  79. 	}
  80. 	return dist[rd][cd];
  81. }
  82.  
  83. int main()
  84. { 
  85.     while(cin>>r>>c)
  86.     {
  87.  
  88.     	for(int i=1;i<=r;i++)
  89.     	{
  90.     		for(int j=1;j<=c;j++)
  91.     		{
  92.     			cin>>crnt[i][j];
  93.     		}
  94.     	}
  95.     cin>>t;
  96.     while(t--)
  97.     {
  98.     	cin>>rs>>cs>>rd>>cd;
  99.     	memset(status,0,sizeof(status[0][0])*max*max);
  100.     	cout<<dijkstra()<<"\n";
  101.  
  102.     }
  103.     reset_dist();
  104.     memset(status,0,sizeof(status[0][0])*max*max);
  105.     memset(crnt,' ',sizeof(crnt[0][0])*max*max);
  106.   }
  107.   return 0;
  108.  
  109. }
  110.  
  111.  
Success #stdin #stdout 0.06s 14112KB
comments (?)
stdin
copy 
10 10
6051134354
2321601626
4333237711
7100435246
1073373445
7444061776
7570714166
2261637531
6527302645
2035001421
50
2 3 4 1
8 7 8 6
8 2 10 7
2 5 8 5
2 1 3 1
10 3 6 6
10 6 2 4
10 8 4 5
3 1 5 5
1 4 4 5
10 8 9 7
5 8 3 7
10 8 7 8
2 8 2 9
2 2 10 2
5 5 7 2
8 10 7 3
6 5 3 5
1 10 2 1
1 6 2 10
10 1 7 9
2 2 1 2
5 1 10 9
8 4 1 2
2 6 8 6
5 4 9 8
9 7 4 6
9 10 3 5
6 7 5 4
10 8 10 7
7 10 8 5
8 7 4 6
8 10 5 6
2 5 2 6
6 3 2 4
4 3 3 8
1 1 1 8
4 4 3 1
1 9 7 4
7 8 2 5
9 5 4 9
3 4 7 3
1 6 6 7
3 6 7 7
2 9 10 7
6 3 1 8
9 9 5 6
1 2 6 2
9 4 5 2
8 8 2 7
5 5
04125
03355
64734
72377
02062
3
4 2 4 2
4 5 1 4
5 3 3 4
stdout
copy 
2
1
3
3
1
3
3
3
1
1
1
2
3
0
3
2
4
2
5
0
4
1
3
3
3
2
2
4
2
1
2
1
2
1
2
2
3
2
2
3
2
2
2
1
5
3
3
3
2
3
0
2
1
https://ideone.com/EO771i
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!