ESJAIL #modifiedDFS

One of the coolest question I have solved.

Question kehna kya chahta hai :

There is a prisoner, say Gabru. There is a prison with N chambers. In each chamber, there might be a locked door or an open door. And the key to that door will be in another chamber. For example the key to chamber 7 is in chamber 2. Needless to say, Gabru cannot pass through a locked door without first finding the key of that door. There are M corridors. Each corridor joins exactly two chambers.  Gabru has to reach the Nth chamber to escape.

Can Gabru escape?


Concept:

Do DFS on the first chamber. If you reach a locked door, MARK that locked door by maintaining an array to check if the door is locked or open. If you reach a key, check if the door that the key opens is marked or not. If the door is marked, that means now we can open that door and traverse all the corridors adjacent to it. So do another DFS from the door just unlocked.

Keep repeating this. Find key. Check if door marked. If marked, start DFS from there.

Why does this work? 

DFS is used to find the reachability of the nodes of the graph from a single source. So find the keys using DFS and unlock the corresponding door IF you can reach the door from the first chamber.

Code:

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define p(i) cout<<i<<endl;
#define M(x) memset(x,0,sizeof(x))
vector<int> *graph;
int n,k,m,a,b,*check;
int *key,*locked;
bool flag=false;

void dfs(int s) {
//    cout<<s<<" "<<locked[s]<<endl;
    check[s]=1; 
    if(locked[s]||flag) return;
   
    if(key[s] && check[key[s]]&&locked[key[s]]) { locked[key[s]]=0; dfs(key[s]);}
    if(key[s]) locked[key[s]]=0;
    if(s==n) {flag=true; return;}
    for(auto i:graph[s]){
        if(!check[i]) { dfs(i);}
    }
}
   

int main() {
    while(1){
        flag=false;
        cin>>n>>k>>m;
       
        if(n==-1) return 0;
        check=new int[n+1];
        locked=new int[n+1];
        key=new int[n+1];
        M(check);
        M(locked);
        M(key);
        graph = new vector<int>[n+1];
        REP(i,1,k){
            cin>>a>>b;
            if(b==n) continue;
            locked[b]=1;
            key[a]=b;
        }
       
        REP(i,1,m){
            cin>>a>>b;
        //    p(a);
        //    p(b);
            if(find(graph[b].begin(),graph[b].end(),a)==graph[b].end())
            graph[b].push_back(a);
            if(find(graph[a].begin(),graph[a].end(),b)==graph[a].end())
            graph[a].push_back(b);
        }
       
        dfs(1);
       
        if(flag)
        cout<<"Y\n";
        else
        cout<<"N\n";
    }
    return 0;
}