CSES Labyrinth TLEs in Java and Python

Revision en1, by rohantrix, 2021-09-04 13:10:17

Both the codes in Java and Python TLE on CSES for same test cases (7-10). Please help me resolve this issue.

Java:

    static void solve(FastReader sc) {
        int n = sc.nextInt(), m = sc.nextInt();
        char mat[][] = new char[n][m];
        char dir[][] = new char[n][m];
        fill2D(dir, '#');
        int si = 0, sj = 0;
        for (int i = 0; i < n; i++) {
            char a[] = sc.next().toCharArray();
            for (int j = 0; j < m; j++) {
                if (a[j] == 'A') {
                    si = i;
                    sj = j;
                } else if (a[j] == 'B') {
                    endi = i;
                    endj = j;
                }
            }
            mat[i] = a;
        }
        
        boolean f = false;
        Queue<pair> q = new LinkedList<>();
        q.offer(new pair(si, sj));
        while (!q.isEmpty()) {
            pair tmp = q.poll();
            // System.out.println(tmp);
            if (tmp.x == endi && tmp.y == endj) {
                f = true;
                break;
            }
            mat[tmp.x][tmp.y] = '#';

            int nx, ny;
            // Left

            nx = tmp.x;
            ny = tmp.y - 1;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'L';
            }

            // Right

            nx = tmp.x;
            ny = tmp.y + 1;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'R';
            }

            // Up
            nx = tmp.x - 1;
            ny = tmp.y;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'U';
            }
            // Down
            nx = tmp.x + 1;
            ny = tmp.y;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offer(new pair(nx, ny));
                dir[nx][ny] = 'D';
            }
            // System.out.println(q);
        }
        StringBuilder s = new StringBuilder();
        if (!f)
        System.out.println("NO");
        else {
            int nx = endi, ny = endj;
            while(nx!=si || ny!=sj)
            {
                s.append(dir[nx][ny]);
                switch(dir[nx][ny])
                {
                    case 'L':{ny++;break;}
                    case 'R':{ny--;break;}
                    case 'U':{nx++;break;}
                    case 'D':{nx--;break;}
                }
            }
            s.reverse();
            System.out.println("YES");
            System.out.println(s.length());
            System.out.println(s.toString());
        }
        // for (int i = 0; i < n; i++) {
        // for (int j = 0; j < m; j++) {
        // sc.print(dir[i][j]);
        // }
        // sc.println();
        // }
        /*
         * for(int i = 0;i<n;i++) { for(int j = 0; j<m;j++) { sc.print(mat[i][j]); }
         * sc.println(); }
         */

    }

Python :


from collections import deque n,m = map(int,input().split()) mat = [] si = sj = 0 endi = endj = 0 for i in range(n): l = list(input()) for j in range(m): if l[j]=='A': si,sj = i,j if l[j]=='B': endi, endj = i,j mat.append(l) f = False q = deque() dir = [["#" for i in range(m)] for i in range(n)] q.append([si,sj]) while(len(q)!=0): tmp = q.popleft() if (tmp[0] == endi and tmp[1] == endj): f = True break x = tmp[0] y = tmp[1] mat[x][y] = '#' nx = ny = 0 # Left nx = x ny = y-1 if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')): q.append([nx,ny]) dir[nx][ny] = 'L' # Right nx = x ny = y+1 if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')): q.append([nx,ny]) dir[nx][ny] = 'R' # Up nx = x-1 ny = y if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')): q.append([nx,ny]) dir[nx][ny] = 'U' # Down nx = x+1 ny = y if (not(nx < 0 or nx >= n or ny < 0 or ny >= m or mat[nx][ny] == '#')): q.append([nx,ny]) dir[nx][ny] = 'D' if not f: print("NO") else: s = [] nx,ny = endi, endj while nx!=si or ny!=sj: s.append(dir[nx][ny]) c = dir[nx][ny] if c=='L': ny+=1 elif c=='R': ny-=1 elif c=='U': nx+=1 else: nx-=1 print("YES") print(len(s)) print(*s[::-1], sep='')
Tags #tle, #cses, #graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English rohantrix 2021-09-04 19:58:51 2839
en2 English rohantrix 2021-09-04 19:56:19 9 Tiny change: 'Both the c' -> '[SOLVED] Both the c'
en1 English rohantrix 2021-09-04 13:10:17 4962 Initial revision (published)