ekanshlohiya98

shortest_path_with_landmines

May 23rd, 2022 (edited)
155
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. https://www.geeksforgeeks.org/find-shortest-safe-route-in-a-path-with-landmines/
  3.  
  4. Given a path in the form of a rectangular matrix having few landmines arbitrarily placed (marked as 0), calculate length of the shortest safe route possible from any cell in the first column to any cell in the last column of the matrix. We have to avoid landmines and their four adjacent cells (left, right, above and below) as they are also unsafe. We are allowed to move to only adjacent cells which are not landmines. i.e. the route cannot contains any diagonal moves.
  5.  
  6. Examples:  
  7.  
  8. Input:
  9. A 12 x 10 matrix with landmines marked as 0
  10.  
  11. [ 1  1  1  1  1  1  1  1  1  1 ]
  12. [ 1  0  1  1  1  1  1  1  1  1 ]
  13. [ 1  1  1  0  1  1  1  1  1  1 ]
  14. [ 1  1  1  1  0  1  1  1  1  1 ]
  15. [ 1  1  1  1  1  1  1  1  1  1 ]
  16. [ 1  1  1  1  1  0  1  1  1  1 ]
  17. [ 1  0  1  1  1  1  1  1  0  1 ]
  18. [ 1  1  1  1  1  1  1  1  1  1 ]
  19. [ 1  1  1  1  1  1  1  1  1  1 ]
  20. [ 0  1  1  1  1  0  1  1  1  1 ]
  21. [ 1  1  1  1  1  1  1  1  1  1 ]
  22. [ 1  1  1  0  1  1  1  1  1  1 ]
  23.  
  24. Output:  
  25. Length of shortest safe route is 13 (Highlighted in Bold)
  26. */
  27.  
  28.  
  29. #include<bits/stdc++.h>
  30. using namespace std;
  31. typedef long long ll;
  32. typedef long double ld;
  33. #define pb push_back
  34. #define mp make_pair
  35. #define vpll vector<pair<ll,ll>>
  36. #define vll vector<ll>
  37. #define mpll map<ll,ll>
  38. #define all(x) x.begin(),x.end()
  39. #define sortall(x) sort(x.begin(),x.end())
  40. #define line cout<<'\n'
  41. #define fo(i,n) for(int i=0;i<n;i++)
  42. #define foe(i,a,n) for(int i=a;i<n;i++)
  43. #define fr(i,n) for(int i=n-1;i>=0;i--)
  44. #define cy cout<<"YES"<<endl
  45. #define cn cout<<"NO"<<endl
  46. #define debug(x) cout<<x<<endl
  47. #define print(x) cout<<x<<" "
  48. #define deb(x,y) cout<<x<<" "<<y<<endl
  49. #define MOD 1000000007
  50. const int N1=100001;
  51. bool isPrime[N1];
  52. void sieve()
  53. {
  54.     memset(isPrime, true, sizeof(isPrime));
  55.     for (int p = 2; p * p <= N1; p++)
  56.     {
  57.         if (isPrime[p] == true)
  58.         {
  59.             for (int i = p * p; i <= N1; i += p)
  60.                 isPrime[i] = false;
  61.         }
  62.     }
  63. }
  64. long long power(long long a, long long b) {
  65.     if (b == 0)
  66.         return 1;
  67.     long long res = power(a, b / 2);
  68.     if (b % 2)
  69.         return res * res * a;
  70.     else
  71.         return res * res;
  72. }
  73. /*====================================================================================*/
  74. int mn;
  75.  
  76. bool isSafe(int x, int y, vector<vector<int>> &field)
  77. {
  78.     int n=field.size();
  79.     int m=field[0].size();
  80.     if(x<0 || y<0 || x>=n || y>=m) return false;
  81.     if(field[x][y]==0 || field[x][y]==2) return false;
  82.     if(x-1>=0 && field[x-1][y]==0) return false;
  83.     if(y-1>=0 && field [x][y-1]==0) return false;
  84.     if(x+1<n && field[x+1][y]==0) return false;
  85.     if(y+1<n && field[x][y+1]==0) return false;
  86.     return true;
  87. }
  88.  
  89. void solve(int x,int y,int moves,vector<vector<int>> &field)
  90. {
  91.     int n=field.size();
  92.     int m=field[0].size();
  93.     if(y==m-1)
  94.     {
  95.         mn=min(mn,moves);
  96.         return;
  97.     }
  98.     if(isSafe(x,y,field))
  99.     {
  100.         field[x][y]=2;
  101.  
  102.         solve(x+1,y,moves+1,field);
  103.         solve(x,y+1,moves+1,field);
  104.         solve(x-1,y,moves+1,field);
  105.         solve(x,y-1,moves+1,field);
  106.  
  107.         field[x][y]=1;
  108.     }
  109. }
  110.  
  111.  
  112. int main()
  113. {
  114.     ios_base::sync_with_stdio(false);
  115.     cin.tie(NULL);
  116.     ll t=1;
  117.     cin>>t;
  118.  
  119.     while(t--)
  120.     {
  121.         mn=INT_MAX;
  122.         int n,m; cin>>n>>m;
  123.         vector<vector<int>> field(n,vector<int>(m));
  124.         fo(i,n)
  125.         {
  126.             fo(j,m)
  127.             {
  128.                 cin>>field[i][j];
  129.             }
  130.         }
  131.         fo(i,n)
  132.         {
  133.             solve(i,0,0,field);
  134.         }
  135.         cout<<mn<<endl;
  136.     }
  137. }
  138.  
RAW Paste Data Copied