-4 -1 is outputting IMPOSSIBLE when a possible path is NSW. As a matter of
fact, all solutions involving 1 and 4, positive and negative, say
IMPOSSIBLE. Maybe the program is failing to account for the fact that you
can use 1 and -2 or -1 and 2 to reach -1 and 1 respectively? Hope this
helps.
Best,
Matt
On Monday, April 20, 2020 at 12:38:18 PM UTC-4, Cheung Scott wrote:
>
> Hi guys, I wrote a straight forward BFS solution to solve 1B Expogo
> question, targeting to solve test set 1 and 2.
> However, not knowing which corner case it fails, the solution got WA.
> Basic cases are all past locally, anyone could advise why below solution
> fails?
>
> import java.util.Arrays;
> import java.util.LinkedList;
> import java.util.Queue;
> import java.util.Scanner;
>
> public class Solution {
>
> private static final int LIMIT = 400; // target at set 2: limit 100,
> loosen a bit
> private static final int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
> private static final String[] ways = {"N", "S", "E", "W"};
>
> private static String solve(int x, int y) {
> int maxStep = (int) (Math.log(LIMIT) / Math.log(2) + 1);
> Queue<int[]> queue = new LinkedList<>();
> boolean[][] visited = new boolean[2*LIMIT+1][2*LIMIT+1];
> String[][] paths = new String[2*LIMIT+1][2*LIMIT+1];
> for (String[] path : paths) Arrays.fill(path, "");
> queue.offer(new int[]{0, 0});
> //visited[LIMIT][LIMIT] = true; // let (0, 0) output IMPOSSIBLE
> int step = 0, dist;
> while (!queue.isEmpty() && step <= maxStep + 3) { // loosen a bit
> int size = queue.size();
> dist = (int) Math.pow(2, step);
> for (int s = 0; s < size; s++) {
> int[] cell = queue.poll();
> if (step > 0 && cell[0] == x && cell[1] == y) return
> paths[x+LIMIT][y+LIMIT]; // let (0, 0) output IMPOSSIBLE
> for (int i = 0; i < 4; i++) {
> int xx = cell[0] + dirs[i][0] * dist;
> int yy = cell[1] + dirs[i][1] * dist;
> if (xx >= -LIMIT && xx <= LIMIT && yy >= -LIMIT && yy
> <= LIMIT && !visited[xx+LIMIT][yy+LIMIT]) {
> visited[xx+LIMIT][yy+LIMIT] = true;
> queue.offer(new int[]{xx, yy});
> paths[xx+LIMIT][yy+LIMIT] =
> paths[cell[0]+LIMIT][cell[1]+LIMIT] + ways[i];
> }
> }
> }
> step++;
> }
> return "IMPOSSIBLE";
> }
>
> public static void main(String[] args) {
> Scanner in = new Scanner((System.in));
> int T = in.nextInt(); // Scanner has functions to read ints,
> longs, strings, chars, etc.
> for (int ks = 1; ks <= T; ++ks) {
> int x = in.nextInt();
> int y = in.nextInt();
> System.out.println("Case #" + ks + ": " + solve(x, y));
> }
> }
> }
>
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/5717e0a9-37c1-4e9b-b4a5-2315ce3a379f%40googlegroups.com.
