fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. int rs,m,n;
  4. void fun(int arr[1000][1000],int i,int j,int r){
  5. 	if(arr[i][j]==3){
  6. 		rs=min(rs,r);
  7. 		return;
  8. 	}
  9. 	arr[i][j]*=-1;
  10. 	if(j-1>=0&&arr[i][j-1]>0)
  11. 		fun(arr,i,j-1,r);
  12. 	if(j+1<n&&arr[i][j+1]>0)
  13. 		fun(arr,i,j+1,r);
  14. 	int t=i-1;
  15. 	while(t>=0 && arr[t][j]==0)
  16. 		t--;
  17. 	if(t>=0&&arr[t][j]>0)
  18.     {
  19.         if(r<i-t)
  20.         {
  21.              fun(arr,t,j,i-t);   
  22.         }
  23.         else
  24.         {
  25.             fun(arr,t,j,r); 
  26.         }
  27.  
  28.  
  29.     }
  30. 	t=i+1;
  31. 	while(t<m&& arr[t][j]==0)
  32. 		t++;
  33. 	if(t<m&&arr[t][j]>0)
  34.     {
  35.         if(r<t-i)
  36.         {
  37.              fun(arr,t,j,t-i);   
  38.         }
  39.         else
  40.         {
  41.             fun(arr,t,j,r); 
  42.         }
  43.     }
  44.     arr[i][j]*=-1;
  45. }
  46. int main() {
  47. 	int t;
  48. 	cin>>t;
  49. 	while(t--){
  50. 		cin>>m>>n;
  51. 		int arr[1000][1000];
  52. 		for(int i=0;i<m;i++)
  53. 			for(int j=0;j<n;j++)
  54. 				cin>>arr[i][j];
  55. 		rs=n;
  56. 		fun(arr,m-1,0,0);
  57. 		cout<<rs<<endl;
  58. 	}
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
1
5 8
1 1 1 1 0 0 1 0
0 0 0 1 0 1 1 3
1 1 1 0 0 1 0 0
0 0 0 0 0 0 1 0
2 1 1 1 1 1 1 1
stdout
copy 
2
https://ideone.com/vPwr7k
language:
C++ (gcc 8.3)
created:
4 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!