fork(2) download
copy 
  1.  
  2. /**
  3. AUTHOR:Rahul Shah
  4. LINK:
  5. WEBSITE:Directi Internship
  6. PROBLEM:
  7. **/
  8.  
  9. #include<iostream>
  10. #include<cstdio>
  11. #include<algorithm>
  12. #include<vector>
  13. #include<map>
  14. #include<cmath>
  15. #include<cstring>
  16. #include<stack>
  17. #include<climits>
  18. #include<cstdlib>
  19. using namespace std;
  20. #define MOD 1000000007
  21. #define ll long long
  22. ll int a[101][101];
  23. int vi,vj,n,m,k;
  24. int vis[101][101];
  25. ll int dis[101][101];
  26. int abs(int a)
  27. {
  28. 	return a>0?a:-a;
  29. }
  30. ll int f(int i,int j)
  31. {
  32. //	cout<<i<<" "<<j<<"\n";
  33. 	ll int d1=9999999LL*9999999,d2=9999999LL*9999999,d3=9999999LL*9999999,d4=9999999LL*9999999;
  34. 	vis[i][j]=1;
  35. 	if(i==vi&&j==vj)
  36. 	{
  37. 		return 1;
  38. 	}
  39. 	if(i+1<n&&!vis[i+1][j]&&abs(a[i+1][j]-a[i][j])<=k)
  40. 	{
  41. 	 	if(dis[i][j]!=0)
  42. 	 	{
  43. 	 		d1=dis[i+1][j];
  44. 	 	}
  45. 	 	else 
  46. 	 		d1=f(i+1,j);
  47. 	}
  48. 	if(j+1<m&&!vis[i][j+1]&&abs(a[i][j+1]-a[i][j])<=k)
  49. 	{
  50. 		if(dis[i][j]!=0)
  51. 	 	{
  52. 	 		d2=dis[i][j+1];
  53. 	 	}
  54. 	 	else
  55. 			d2=f(i,j+1);
  56. 	}
  57.  
  58. 	if(i-1>=0&&!vis[i-1][j]&&abs(a[i-1][j]-a[i][j])<=k)
  59. 	{
  60. 	 	if(dis[i-1][j]!=0)
  61. 	 	{
  62. 	 		d3=dis[i-1][j];
  63. 	 	}
  64. 	 	else
  65. 	 		d3=f(i-1,j);
  66. 	}
  67. 	if(j-1>=0&&!vis[i][j-1]&&abs(a[i][j-1]-a[i][j])<=k)
  68. 	{
  69. 		if(dis[i][j-1]!=0)
  70. 	 	{
  71. 	 		d4=dis[i][j-1];
  72. 	 	}
  73. 	 	else 
  74. 			d4=f(i,j-1);
  75. 	}
  76. 	vis[i][j]=0;
  77. 	return dis[i][j]=(1+min(d1,min(d2,min(d3,d4))));
  78. }
  79. int main()
  80. {
  81. 	int t;
  82. 	cin>>t;
  83. 	while(t--)
  84. 	{
  85. 	//	int n,m;
  86. 		cin>>n>>m;
  87. 	//	int vi,vj;
  88. 		cin>>vi>>vj;
  89. 		scanf("%d",&k);
  90. 		for(int i=0;i<n;i++)
  91. 		{
  92. 			for(int j=0;j<m;j++)
  93. 			{
  94. 				a[i][j]=vis[i][j]=dis[i][j]=0;
  95. 			}
  96. 		}
  97. 		for(int i=0;i<n;i++)
  98. 			for(int j=0;j<m;j++)
  99. 			{
  100. 				a[i][j]=vis[i][j]=0;
  101. 			}
  102. 		for(int i=0;i<n;i++)
  103. 		{
  104. 			for(int j=0;j<m;j++)
  105. 			{
  106. 				scanf("%d",&a[i][j]);
  107. 			}
  108. 		}
  109. 		vi--;vj--;
  110. 		ll int ans=f(0,0);
  111. 		if(vis[vi][vj]==0)
  112. 			printf("-1\n");
  113. 		else
  114. 			printf("%lld\n",ans-2);
  115.  
  116.  
  117. 	}
  118. return 0;
  119. }
Runtime error #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3heWeO
language:
C++ (gcc 8.3)
created:
9 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!