fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int dist=INT_MAX;
  7.  
  8.  
  9. void bfs(int god_node,vector<vector<int>>&graph,vector<bool>&visited,vector<int>&values){
  10.     visited[god_node]=true;
  11.     int n=graph.size();
  12.     vector<int>lvl(n,-1);
  13.     lvl[god_node]=-1;
  14.  
  15.     queue<int>q;
  16.     q.push(god_node);
  17.  
  18.     while(!q.empty()){
  19.         int node=q.front();
  20.         q.pop();
  21.  
  22.         for(auto&child:graph[node]){
  23.             if(!visited[child]){
  24.                 visited[child]=true;
  25.                 lvl[child]=lvl[node]+1;
  26.                 q.push(child);
  27.             }
  28.         }
  29.     }
  30.  
  31.     for(int i=0;i<n;i++){
  32.         if(values[i]==3){
  33.             //cout<<"Distance till moment: "<<lvl[i]<<endl;
  34.             dist=min(dist,lvl[i]);
  35.         }
  36.     }
  37.  
  38.  
  39. }
  40.  
  41. bool valid(int i,int j,int n,int m){
  42.     if(i>=0 && i<n && j>=0 && j<m){
  43.         return true;
  44.     }
  45.  
  46.     return false;
  47. }
  48.  
  49. void print(vector<int>a){
  50.     int n=a.size();
  51.     for(int i=0;i<n;i++){
  52.         cout<<a[i]<<" ";
  53.     }
  54.     cout<<endl;
  55. }
  56.  
  57. int main(){
  58.     int n,m;
  59.     cin>>n>>m;
  60.     vector<vector<int>>nodes(n,vector<int>(m,0));
  61.     vector<vector<int>>grid(n,vector<int>(m));
  62.     int cnt=0;
  63.     for(int i=0;i<n;i++){
  64.         for(int j=0;j<m;j++){
  65.             cin>>grid[i][j];
  66.             nodes[i][j]=cnt;
  67.             cnt++;
  68.         }
  69.     }
  70.  
  71.     vector<int>values(n*m,0);
  72.     vector<vector<int>>graph(n*m+1);
  73.  
  74.     for(int i=0;i<n;i++){
  75.         for(int j=0;j<m;j++){
  76.             int node=nodes[i][j];
  77.             int val=grid[i][j];
  78.  
  79.             if(valid(i-1,j,n,m)){
  80.                 int child=nodes[i-1][j];
  81.                 graph[node].push_back(child);
  82.             }
  83.  
  84.             if(valid(i+1,j,n,m)){
  85.                 int child=nodes[i+1][j];
  86.                 graph[node].push_back(child);
  87.             }
  88.  
  89.             if(valid(i,j-1,n,m)){
  90.                 int child=nodes[i][j-1];
  91.                 graph[node].push_back(child);
  92.             }
  93.  
  94.             if(valid(i,j+1,n,m)){
  95.                 int child=nodes[i][j+1];
  96.                 graph[node].push_back(child);
  97.             }
  98.  
  99.             values[node]=val;
  100.         }
  101.     }
  102.  
  103.     int god_node=n*m;
  104.  
  105.     int s=graph.size();
  106.     for(int i=0;i<s;i++){
  107.         if(values[i]==2){
  108.             graph[god_node].push_back(i);
  109.         }
  110.     }
  111.  
  112.     //print(graph[god_node]);
  113.  
  114.     /*for(int i=0;i<n*m;i++){
  115.         print(graph[i]);
  116.     }
  117.  
  118.     */
  119.  
  120.     vector<bool>visited(n*m+1,false);
  121.     bfs(god_node,graph,visited,values);
  122.     cout<<"Minimum distance: "<<dist<<endl;
  123.  
  124.     return 0;
  125. }
Success #stdin #stdout 0.01s 5220KB
comments (?)
stdin
copy 
5 5 
0 2 0 2 0 
0 0 0 0 0 
0 0 0 0 0 
0 0 0 3 0 
0 0 0 0 0
stdout
copy 
Minimum distance: 3
https://ideone.com/BjtQl7
language:
C++ (gcc 8.3)
created:
1 day 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!