19 months ago

Viswanath • 20

Hyderabad

Q1)

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int shortest_time(int n,int m,vector<vector<int>>&matrix,int p){
  vector<vector<int>>distance(n,vector<int>(m,INT_MAX));
  set<pair<int,pair<int,int>>>s;
  distance[0][0]=0;
  s.insert({0,{0,0}});
  int drow[]={0,0,1,-1};
  int dcol[]={1,-1,0,0};
  while(!s.empty()){
      auto it=s.begin();
      int r=(*it).second.first;
      int c=(*it).second.second;
      int d=(*it).first;
      s.erase(it);
      for(int i=0;i<=3;i++){
         int r1=r+drow[i];
         int c1=c+dcol[i];
         if(0<=r1&&r1<n&&0<=c1&&c1<m&&(matrix[r1][c1]==p||matrix[r1][c1]==0)&&1+d< distance[r1][c1]){
             distance[r1][c1]=min(distance[r1][c1],1+d);
             
             if(r1==n-1&&c1==m-1){
                 return 1+d;
             }
             s.insert({distance[r1][c1],{r1,c1}});
         }
      }
     
  }
   return -1;
}
int main()
{
   int n,m;
   cin>>n>>m;
   vector<vector<int>>maze(n,vector<int>(m,0));
   for(int i=0;i<n;i++){
       for(int j=0;j<m;j++){
           char k;
           cin>>k;
           if(k=='*'){
               maze[i][j]=1;
               
           }else if(k=='#'){
               maze[i][j]=2;
           }else{
               maze[i][j]=0;
           }
       }
   }
   int p1=shortest_time(n,m,maze,1);
   int p2=shortest_time(n,m,maze,2);
   cout<<p1<<endl;
   cout<<p2<<endl;
}