Thank you very much, this do help. I just realize that straightforward BFS
doesn't work for such scenario where each step is not at a fixed distance.
在 2020年4月21日星期二 UTC+8上午6:05:54，Matt Fenlon写道：
>
> -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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/c38724e3-0818-47df-b62d-51f3fe630378%40googlegroups.com.
