This question is gonna kill me : QUEEN #modifiedBFS #dijkstra Bonus Question : MLASERP

Took me 3 hours to do this one. But ahem! TLE TLE TLE I dont know what the hell is the matter with this. So I tried a similar problem with the same code and it was Accepted. Screw spoj.


So coming back to the topic!

Aakhir ye question kehna kya chahta hai?

There is a chess board with R rows and C columns. On the board there is one queen (obviously given the name of the problem) and obstacles. You are given the initial postion (S) and target position (F) of the queen.


Tell the minimum number of moves to reach the target.

Concept

I solved it using two methods but I'll tell the one using BFS.


If the queen is moving in the same direction, then no extra moves are needed to move it one more step but ifit changes its direction, one more move is needed. So with each move we have 3 parameters attached,



                          <Moves it now, x co-ordinate, y co-ordinate>


Now a simple method is to let the queen move in any one direction one by one stepwise. At each step, it can be counted as same move, so no new move is needed. So move the queen in all 8 directions one step wise and add each step to the queue as the current number of moves + 1.

Keep moving in a direction till



1. No obstacle

2. Within board

3. No visited cell with less moves than current


I'll explain the 3rd one. Suppose you reach a cell that you've already travelled to but with less moves, going on that cell again is redundant. So make an array of visited[][] to store the min moves to reach that cell.

Code

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define ppi pair<int,pair<int,int> >
#define ppp pair<int,pair<int,pair<int,int> > >
#define mp make_pair
#define INF 1e8
#define M(x,a) memset(x,a,sizeof(x))
using namespace std;

char grid [1005][1005];
int vis [1005][1005];
int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,1,0,-1,1,-1,1,-1},R, C,sx,sy,fx,fy;

int bfs(){
   
    queue<ppi> q;
    q.push(mp(0,mp(sx,sy)));
    vis[sx][sy]=0;
    while(!q.empty()){
        ppi temp=q.front();
        q.pop();
        int dist=temp.first,f=temp.second.first,s=temp.second.second;
        if(f==fx&&s==fy) return dist;
        if(dist>vis[f][s]||grid[f][s]=='X'||vis[f][s]==-1) continue;
        int j=1;
        REP(i,0,7){
            j=1;
            while(1){
            int xx=f+dx[i]*j,yy=s+dy[i]*j;
            if(xx>=0 &&xx<=R-1&&yy>=0&&yy<=C-1 && grid[xx][yy]!='X'){
                if(vis[xx][yy]>dist+1 ||vis[xx][yy]==-1) {
                    vis[xx][yy]=dist+1;
                    q.push(mp(dist+1,mp(xx,yy)));
                }
               
            }
            else break;
            j++;
            }
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
    int t;
    scanf("%d",&t);
    while(t--){
        M(vis,-1);
        scanf("%d %d",&R,&C);
        REP(i,0,R-1) scanf("%s",grid[i]);
        REP(i,0,R-1) REP(j,0,C-1){
                if (grid[i][j]=='S')  
                    sx = i,sy=j;
                else if (grid[i][j]=='F')
                    fx = i,fy=j;
        }
       
        printf("%d\n", bfs());
    }
}

Similar problem : MLASERP

Then I solved a similar problem with a funny statement called MLASERP with cows who want to take using periscope and mirrors. Anywhoo, the code:

CODE :

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define ppi pair<int,pair<int,int> >
#define ppp pair<int,pair<int,pair<int,int> > >
#define mp make_pair
#define INF 1e8
#define M(x,a) memset(x,a,sizeof(x))
using namespace std;

char grid [1005][1005];
int vis [1005][1005];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},R, C,sx,sy,fx,fy;

int bfs(){
   
    queue<ppi> q;
    q.push(mp(0,mp(sx,sy)));
    vis[sx][sy]=0;
    while(!q.empty()){
        ppi temp=q.front();
        q.pop();
        int dist=temp.first,f=temp.second.first,s=temp.second.second;
    //    cout<<f<< " "<<s<<" "<<dist<<endl;
        if(f==fx&&s==fy) return dist;
        if(dist>vis[f][s]||grid[f][s]=='*'||vis[f][s]==-1) continue;
        int j=1;
        REP(i,0,3){
            j=1;
            while(1){
            int xx=f+dx[i]*j,yy=s+dy[i]*j;
            if(xx>=0 &&xx<=R-1&&yy>=0&&yy<=C-1 && grid[xx][yy]!='*'){
                if(vis[xx][yy]>dist+1 ||vis[xx][yy]==-1) {
                    vis[xx][yy]=dist+1;
                    q.push(mp(dist+1,mp(xx,yy)));
                }
               
            }
            else break;
            j++;
            }
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(0);
   sx=-1;
   {
        M(vis,-1);
        scanf("%d %d",&R,&C);
        swap(R,C);
        REP(i,0,R-1) scanf("%s",grid[i]);
        REP(i,0,R-1) REP(j,0,C-1){
                if (grid[i][j]=='C'){  
                if(sx==-1)
                    sx = i,sy=j;
                else
                    fx = i,fy=j;
                }
        }
       
        printf("%d\n", bfs()-1);
    }
}