Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

The problem description is from ACM Timus Online Judge. (1930. Ivan's Car)

My first idea is using BFS. But it keeps getting Wrong Answer at Test 6. Any hints to solve this? The following is my Java code.

import java.io.*;
import java.util.*;

class ss  // BFS node to put in the Queue
{
    public int id;  // town id
    public int depth;   // how many gear changes
    public int prev;   // previous town

    public ss(int _id, int _d, int _p)
    {
        this.id = _id;
        this.depth = _d;
        this.prev = _p;
    }
}

public class tsss
{
    static ArrayList<Integer>[] towns;  
    static ArrayList<Integer>[] tt;
    static boolean[] vis;  // has been visited before ?

    static boolean up(int a, int b)
    {
        for (int i = 0; i < tt[a].size(); i ++)
        {
            if (tt[a].get(i) == b)
            {
                return true;  // from this go uphill
            }
        }
        return false;  // from this go downhill
    }

    static boolean change(int p, int cur, int next)
    {
        if (p == -1)
        {
            return false;  // at the beginning you can turn on any gear modes
        }
        return (up(p, cur) != up(cur, next));
    }

    static int search(int a, int b)
    {
        if (a == b)
        {
            return 0;
        }
        Queue q = new LinkedList<ss>();
        q.add(new ss(a, 0, -1)); // push the first node
        Arrays.fill(vis, false);
        vis[a] = true;
        while (q.size() > 0) 
        {
            ss k = (ss)q.poll();
            int x = k.id;
            int prev = k.prev;
            for (int i = 0; i < towns[x].size(); i ++)  // its children nodes
            {
                int y = (int)towns[x].get(i);
                if (y == b)
                {
                    if (change(prev, x, y))
                    {
                        return k.depth + 1;
                    }
                    return k.depth;
                }
                if (!vis[y])  // not visited before
                {
                    vis[y] = true;
                    if ((change(prev, x, y)))  // one gear change
                    {
                        q.add(new ss(y, k.depth + 1, x));
                    }
                    else
                    {
                        q.add(new ss(y, k.depth, x));
                    }
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
        String[] s = rr.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        towns = new ArrayList[n + 1];
        tt = new ArrayList[n + 1];
        vis = new boolean[n + 1];
        for (int i = 0; i < n + 1; i ++)
        {
            tt[i] = new ArrayList<Integer>();
            towns[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i ++)
        {
            s = rr.readLine().split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            towns[x].add(y);
            tt[x].add(y);
            towns[y].add(x);
        }
        s = rr.readLine().split(" ");
        int a = Integer.parseInt(s[0]);
        int b = Integer.parseInt(s[1]);
        System.out.print(search(a, b));
    }
}
share|improve this question

closed as off topic by Corbin, svick, Brian Reichle, Glenn Rogers, Eva Jan 16 '13 at 10:48

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
It's a shame this question has been closed! I would be very happy to discuss and compare approaches to this if you are interested. Can I send you an e-mail to the address provided on your website? –  us2012 Jan 16 '13 at 14:42
    
sure... and i also set up a forum to discuss the solutions. rot47.net/q –  DoctorLai Jan 16 '13 at 15:17
    
Okay, I have set up an account there. –  us2012 Jan 16 '13 at 16:01
    
thanks.. great hint... I'll try later. –  DoctorLai Jan 16 '13 at 17:45
    
Hi us2012, finally got accepted. rot47.net/_acm/viewtopic.php?f=3&t=2 –  DoctorLai Jan 18 '13 at 15:32

1 Answer 1

It seems to me that your BFS finds the shortest path in terms of roads used (and then returns the number of up/down changes in that path), instead of finding the shortest path in terms of up/down changes.

For example, consider the following:

a -up-> b -down-> z
|                 ^
up                |
|                 up
v                 |
c -up->  d  -up-> e

Then the solution of the problem is 0 gear changes, using the path acdez, while your algorithm returns the path abz with one gear change.

edit: Looking at your submission history on Timus, it looks like you had a solution that made it up to test case 11. Why did you abandon that? (Funnily enough, my first solution is stuck at 11 as well :) This is a fun problem, it seems so obvious and yet something's missing).

share|improve this answer
    
Thank you, this is something I didn't notice before. I will try a new solution. Maybe BFS isn't correct. –  DoctorLai Jan 16 '13 at 11:13
    
thanks.. got accepted using a PriorityQueue, always poping the minimal every time. rot47.net/_acm/viewtopic.php?f=3&t=2 –  DoctorLai Jan 18 '13 at 15:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.