JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
The code execution time exceeded the 2 second time limit for example 4! | Reply
Only the example can not pass, but i really don't how to optimize the code any more.
Could you please help me :)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
public class grafixMask {
    private boolean[][] bitmap = new boolean[400][600];
    public int[] sortedAreas(String[] rectangles) {
        setRec(rectangles);
 
        List<Integer> list = new ArrayList<Integer>();
 
        for (int i = 0; i < 400; i++) {
            for (int j = 0; j < 600; j++) {
                if (!bitmap[i][j]) {
                    list.add(bfs(i, j));
                }
            }
 
        }
        Collections.sort(list);
        int[] result = new int[list.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        }
        return result;
    }
    public int bfs(int x, int y) {
        int[][] queue = new int[400 * 600][2];
        int put = 0, get = 0;
        queue[0][0] = x;
        queue[0][1] = y;
        bitmap[x][y] = true;
        put++;
        int count = 0;
        while (get < put) {
            int px = queue[get][0];
            int py = queue[get][1];
            get++;
            int[][] adj = getAdj(px, py);
            for (int i = 0; i < adj.length; i++) {
                int ax = adj[i][0], ay = adj[i][1];
                if (inEdge(ax, ay) && !bitmap[ax][ay]) {
                    bitmap[ax][ay] = true;
                    queue[put][0] = ax;
                    queue[put][1] = ay;
                    put++;
                }
            }
            count++;
        }
        return count;
    }
    
    public void setRec(String[] rectangles) {
        int[] rec = new int[4];
        for (String s : rectangles) {
            String[] ss = s.split(" ");
            for (int i = 0; i < 4; i++) {
                rec[i] = Integer.parseInt(ss[i]);
            }
            for (int i = rec[0]; i <= rec[2]; i++) {
                for (int j = rec[1]; j <= rec[3]; j++) {
                    bitmap[i][j] = true;
                }
            }
        }
    }
    public boolean inEdge(int x, int y) {
        return x >= 0 && x < 400 && y >= 0 && y < 600;
    }
    public int[][] getAdj(int x, int y) {
        int[][] adj = new int[4][2];
        adj[0][0] = x;
        adj[0][1] = y - 1;
        adj[1][0] = x;
        adj[1][1] = y + 1;
        adj[2][0] = x + 1;
        adj[2][1] = y;
        adj[3][0] = x - 1;
        adj[3][1] = y;
        return adj;
    }
}
Re: The code execution time exceeded the 2 second time limit for example 4! (response to post by aisensiy) | Reply
oh, my god, just use a linkedlist instead of array!!
public int bfs(int x, int y) {
        LinkedList<int[]> queue = new LinkedList<int[]>();
        queue.addLast(new int[]{x, y});
        bitmap[x][y] = true;
        int count = 0;
        while (queue.size() != 0) {
            int[] point = queue.poll();
            int px = point[0];
            int py = point[1];
            int[][] adj = getAdj(px, py);
            for (int i = 0; i < adj.length; i++) {
                int ax = adj[i][0], ay = adj[i][1];
                if (inEdge(ax, ay) && !bitmap[ax][ay]) {
                    bitmap[ax][ay] = true;
                    queue.addLast(new int[]{ax, ay});
                }
            }
            count++;
        }
        return count;
    }
RSS