Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com

And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Monday, February 2, 2015

MLASERP-Laser Phones

Laser Phones

Given below code is for MLASERP spoj or laser phones spoj.

Explanation : - 

First find the positions of the cow where they are situated . Now make one of them as source and other one destination . Now start bfs from source an apply bfs in following manner .

1-> for each cell having row = source.row or column = source.column make distance =0 as you need no mirror  and push all that in queue.

2-> Next time whichever node you popped from queue , check if distance of all cell having row =poppedcell.row or column = poppedcell.column is greater then distance filled in poppedcell + 1 , if condition is true then push the node in queue .

Repeat above process till you reach the destination node.


#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int , int >
bool check[109][109];
int main(){
    int n , m;
    cin>>m>>n;
    string s[n+9];
    for(int i = 0 ; i < n ; i++)
        cin>>s[i];

    pii source , dest;
    bool first = 1;
    for(int i = 0 ; i < n  ; i ++){
        for(int j = 0 ; j < m ; j++)
            if(s[i][j] == 'C'){
                if(first)
                    source = mp(i , j) , first = 0;
                else{
                    dest = mp(i , j);
                    break;
                }
            }
    }
    
    queue<pair<int , int > > q;
    q.push(source);
    int res = 0;
    int dist[109][109];
    for(int i = 0 ; i < 109 ; i++)
        for(int j = 0 ; j < 109 ; j++)
            dist[i][j] = INT_MAX;

    dist[source.first][source.second]=0;
    while(!q.empty()){
        int i , j ; 
        i = q.front().first;
        j = q.front().second;
        int u = i, v = j;
        while(u+1 < n && s[u+1][j]!='*'  ){
            if( dist[u+1][j] > dist[i][j] + 1){
                q.push(mp(u+1 , j));
                dist[u+1][j] = dist[i][j] +1;
            }
            u++;
        }
        u = i;
        while(u-1 >=0 && s[u-1][j]!='*'  ){
            if(dist[u-1][j] > dist[i][j] + 1){
                q.push(mp(u-1 , v) );
                dist[u-1][j] = dist[i][j] +1;
            }
            u--;
        }
        while(v+1 < m && s[i][v+1]!='*' ){
            if( dist[i][v+1] > dist[i][j] + 1){
                q.push(mp(i , v+1));
                dist[i][v+1] = dist[i][j] +1;
            }
            v++;
        }
        v = j;
        while(v-1 >= 0 && s[i][v-1]!='*'  ){
            if(dist[i][v-1] > dist[i][j] + 1){
                q.push(mp(i , v-1) );
                dist[i][v-1] = dist[i][j] + 1;
            }
            v--;
        }
        q.pop();
    }
    cout<<dist[dest.first][dest.second]-1<<endl;
    return 0;
}

1 comment:

  1. Please clarify the time complexity of the solution is it O(n^2).

    ReplyDelete

Your comment is valuable to us