CSES Labyrinth TLEs in Java and Python

Revision en3, by rohantrix, 2021-09-04 19:58:51

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

Java: [WORKING NOW]

    static int endi, endj;
 
    static void solve() throws IOException{
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        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++) {
            st = new StringTokenizer(br.readLine());
            mat[i] = st.nextToken().toCharArray();
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 'A') {
                    si = i;
                    sj = j;
                } else if (mat[i][j] == 'B') {
                    endi = i;
                    endj = j;
                }
            }
            
        }
        
        boolean f = false;
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.offerLast(new int[]{si, sj});
        while (!q.isEmpty()) {
            int[] tmp = q.pollFirst();
            // System.out.println(tmp);
            if (tmp[0] == endi && tmp[1] == endj) {
                f = true;
                break;
            }
            
 
            int nx, ny;
            // Left
 
            nx = tmp[0];
            ny = tmp[1] - 1;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offerLast(new int[]{nx,ny});
                dir[nx][ny] = 'L';
                mat[nx][ny] = '#';
 
            }
 
            // Right
 
            nx = tmp[0];
            ny = tmp[1] + 1;
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offerLast(new int[]{nx,ny});
                dir[nx][ny] = 'R';
                mat[nx][ny] = '#';
            }
 
            // Up
            nx = tmp[0] - 1;
            ny = tmp[1];
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offerLast(new int[]{nx,ny});
                dir[nx][ny] = 'U';
                mat[nx][ny] = '#';
            }
            // Down
            nx = tmp[0] + 1;
            ny = tmp[1];
            if (!(nx < 0 || nx >= n || ny < 0 || ny >= m || mat[nx][ny] == '#')) {
                q.offerLast(new int[]{nx,ny});
                dir[nx][ny] = 'D';
                mat[nx][ny] = '#';
            }
            // 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();
            output.write("YES\n");
            output.write(s.length() + "\n");
            output.write(s.toString());
        }
        output.flush();

 
    }
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)