JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 211 The code execution time exceeded the 2 second time limit for example 4!
 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 list = new ArrayList();   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 queue = new LinkedList(); 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; } ```
 Forums Algorithm Matches SRM 211 The code execution time exceeded the 2 second time limit for example 4! Previous Thread  |  Next Thread