TLE in CSES problem Labyrinth

general
, ,
1

Link to the problem: CSES - Labyrinth
My Code:

#include <bits/stdc++.h>
using namespace std;
 
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
int main()
{
    FASTIO
    int n, m;
    cin >> n >> m;
    char board[n][m];
    int sr, sc, dr, dc;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 'A')
                sr = i, sc = j;
            else if(board[i][j] == 'B')
                dr = i, dc = j;
        }
    }
    char p[] = {'U','D','R','L'};
    int vr[] = {-1,1,0,0}, vc[] = {0,0,1,-1};
 
    queue<int> rq, cq;
    rq.push(sr);
    cq.push(sc);
 
    bool vis[n][m];
    memset(vis,false,sizeof(vis));
    char parent[n][m];
    parent[sr][sc] = 'x';
    bool reached = false;
    int moves = 0, currNodes = 1, nextNodes = 0;
 
    while(!rq.empty())
    {
        int cr = rq.front();
        int cc = cq.front();
        rq.pop();
        cq.pop();
 
        vis[cr][cc] = true;
        if(cr == dr && cc == dc)
        {
            reached = true;
            break;
        }
        for(int i=0; i<4; i++)
        {
            if(cr+vr[i] < 0 || cc+vc[i] < 0) continue;
            if(cr+vr[i] >= n || cc+vc[i] >= m) continue;
 
            if(vis[cr+vr[i]][cc+vc[i]] || (board[cr+vr[i]][cc+vc[i]] == '#')) continue;
 
            parent[cr+vr[i]][cc+vc[i]] = p[i];
            rq.push(cr+vr[i]);
            cq.push(cc+vc[i]);
            nextNodes++;
        }
        currNodes--;
        if(currNodes == 0)
        {
            currNodes = nextNodes;
            nextNodes = 0;
            moves++;
        }
    }
    if(!reached) cout << "NO\n";
    else
    {
        cout << "YES\n";
        cout << moves << "\n";
        vector<char> path;
        int row = dr, col = dc;
        char c = parent[row][col];
        while(c != 'x')
        {
            path.push_back(c);
            if(c == 'U') c = parent[++row][col];
            else if(c == 'D') c = parent[--row][col];
            else if(c == 'R') c = parent[row][--col];
            else c = parent[row][++col];
        }
        reverse(path.begin(), path.end());
        for(char c : path) cout << c;
        cout << "\n";
    }
    return 0;
}

The above code works well for most of the test cases but fails on the larger test cases like a 1000x1000 grid with all ‘.’ where it gives a TLE. Can anybody please suggest some optimizations?

2

Your BFS is wrong. Vis should be set true when pushing to the queue. Think carefully about what is happening when all are ‘.’.
I edited your code to show how many times it visits each node.
Just input n and m, and you can see how many times it visits each node if it starts from the middle.

Code 
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FASTIO
    int n, m;
    cin >> n >> m;
    char board[n][m];
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            board[i][j] = '.';
        }
    }
    int vr[] = {-1,1,0,0}, vc[] = {0,0,1,-1};
    queue<int> rq, cq;
    rq.push(n/2);
    cq.push(m/2);
    bool vis[n][m];
    memset(vis,false,sizeof(vis));
    vector<vector<int>> count(n, vector<int>(m));
    int ans = 0;
    while(!rq.empty())
    {
        int cr = rq.front();
        int cc = cq.front();
        rq.pop();
        cq.pop();
        ++count[cr][cc];
        ++ans;
        vis[cr][cc] = true;
        for(int i=0; i<4; i++)
        {
            if(cr+vr[i] < 0 || cc+vc[i] < 0) continue;
            if(cr+vr[i] >= n || cc+vc[i] >= m) continue;
            if(vis[cr+vr[i]][cc+vc[i]] || (board[cr+vr[i]][cc+vc[i]] == '#')) continue;
            rq.push(cr+vr[i]);
            cq.push(cc+vc[i]);
        }
    }
    cout<<ans<<"\n";
    for(const auto &vec : count){
        for(const auto &x : vec){
            cout<<x<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

It goes through 3 \times 10^6 nodes for just 21\times 21

3 Likes
3

I haven’t read the question and your code but as everule is saying…it seems like you’re doing the same mistake as this guy-

1 Like