Suggest the optimization

help
, ,
1

Hi ,
This is question which i am solving .

https://cses.fi/problemset/task/1193/

Here is my solution

#include <bits/stdc++.h>
#define  Boost ios_base :: sync_with_stdio (0) ; cin.tie(0) ; cout.tie(0) ;
#define  mod 1000000007 
#define  N   
using namespace std ;
 
struct Pair {
    string path = "" ;
    int cx = 0 ;
    int cy = 0 ;
} ;
 
int n = 0 , m = 0 ;
char c[1001][1001] ;
bool vis[1001][1001] ;
int dx[] = {1,-1,0,0} ;
int dy[] = {0,0,1,-1} ;
 
inline bool valid ( int x , int y ) {
    if ( x < 0 || y < 0 || x > n-1 || y > m-1 || vis[x][y] || c[x][y] == '#' ) 
        return 0 ;
    return 1 ;
}
 
void Go () {
    cin >> n >> m ;
    int sx = -1 , sy = -1 , dex = -1 , dey = -1 ;
    for ( int i = 0 ; i < n ; i++ ) {
        for ( int j = 0 ; j < m ; j++ ) {
            cin >> c[i][j] ;
            if ( c[i][j] == 'A' ) {
                sx = i ;
                sy = j ;
            }   
            else if ( c[i][j] == 'B' ) {
                dex = i ;
                dey = j ;
            }
        }
    }
 
    queue <Pair> q ;
    q.push({"",sx,sy}) ;
 
 
    while ( not q.empty() ) {
        Pair curr = q.front() ;
        q.pop() ;
 
        string putil = curr.path ;
        int cx = curr.cx ;
        int cy = curr.cy ;
 
 
        if ( cx == dex and cy == dey ) {
            cout << "YES\n" << putil.length() << "\n" << putil << "\n" ;
            return ;
        }
 
        for ( int i = 0 ; i < 4 ; i++ ) {
            int nx = cx + dx[i] ;
            int ny = cy + dy[i] ;
            if ( valid(nx,ny) ) {
                char ch ; 
                if ( nx < cx ) {
                    ch = 'U' ;
                }
                else if ( nx > cx ) {
                    ch = 'D' ;
                }
                else if ( ny < cy ) {
                    ch = 'L' ;
                }
                else if ( ny > cy ) {
                    ch = 'R' ;
                }
                vis[nx][ny] = 1 ;
                q.push({putil+ch,nx,ny}) ;
            }
        }
    }
 
    cout << "NO\n" ;
}
 
int32_t main () {
    Boost 
    int t = 1 ;
    // cin >> t ;
    while ( t-- ) {
        Go() ;
    }
    return 0 ;
}

or link to solution
https://cses.fi/paste/02e47f6828fde6fb215266/

I am getting TLE in one testcase .
Plz tell me some optimization for this .
Or some redundant code which can be removed .

2

Time complexity of your code is \mathcal{O}((N+M)\times NM) which is not fast enough to pass in the allowed time limit.

3

How is it O((N+M)*(NM)) ?
For me what I think is it should O(NM) in worst case as I am applying bfs only once.
Or is there any extra TC associated with queue ?

4

You are storing entire path on every node while doing bfs, as when you pass the string by value it creates a copy of that string which can of length N+M in the worst case hence tc is coming out to be cubic

2 Likes
5

Thx Bro as you said .
I changed my code and removed path from pair .
and maintained parent array .
When I reached to destination I generated the path using parent array .
It got AC .

1 Like