Thread: Minedetector, shortest path

What is the correct answer for the map you provided? Knowing your incorrect results doesn't help much, and I don't feel like running Djikstra's algorithm by hand to figure this out. How does the robot know where a mine is? I don't see any on your map. Also, you should work on providing a neater map.

There's a lot code there to swallow. Before you ask others to invest their time to help you might consider:

1) Indentation and whitespace matter (yours could use some work)
2) Give your variables decent names (most of yours have horrible names)
3) Don't use globals unless you MUST. (Your code uses way more than I think it should)
4) Comments matter (it's hard to tell what the intentions are for most of your code. This problem, believe it or not, is made worse by #1, #2 and #3).

There is no correct answer. You just choose a starting point and an ending point. Dijkstra's algorithm will then give you the shortest path. From that path, I have to give the directions between each point.
so for example: If the robot has to go from point 1 to point 16
my code gives the output: 1 5 12 19 18 17 16
Next thing is to give the direction it goes between each step, so it goes straight forward, straight forward, straight forward, left, straight forward, straight forward.

I just found out that my code gives result=3 at the direction fuction, i just dont know why.

Also sorry about the map, i had to make it quickly. I'm going to put some comments in the code so it gets a little bit clearer, thanks!

Originally Posted by mike65535

There's a lot code there to swallow. Before you ask others to invest their time to help you might consider:

1) Indentation and whitespace matter (yours could use some work)
2) Give your variables decent names (most of yours have horrible names)
3) Don't use globals unless you MUST. (Your code uses way more than I think it should)
4) Comments matter (it's hard to tell what the intentions are for most of your code. This problem, believe it or not, is made worse by #1, #2 and #3).

Ok sorry about that, I'm going to edit it now.

Thanks a lot!

Originally Posted by Kurdo

I just found out that my code gives result=3 at the direction fuction, i just dont know why.

Code:

int direction(int a, int b, int c)
{
    int diff[5];
    int result;
   
    diff[0] = points[a].x - points[b].x;
    diff[1] = points[b].x - points[c].x;
    diff[2] = points[c].x - points[a].x;

    diff[3] = points[a].y - points[b].y;
    diff[4] = points[b].y - points[c].y;
    diff[5] = points[c].y - points[a].y;

One cannot access the 6th element in an array that has only 5

Originally Posted by Kurdo

The mines are put in the map randomly.

Yeah but where in your code is a mine looked for? Shouldn't each potential leg along the path be checked with some function you wrote called something like IsMineFound() ?

edit: ok, I see more now...

Originally Posted by mike65535

One cannot access the 6th element in an array that has only 5

Ah yes, your right. But that still didn't solve it

oh yeah i forgot to mention, the mines can only be placed at the dots in the map, not in the cross sections. But that isnt really the problem. The problem is that when i put 1 as source and 16 as destination, the directions that are given to me are wrong.
I'm getting the output: 1 5 4 11 17 16

straight forward - left - straight forward - destination reached

it should be: straight forward - left - straight forward - straight forward - left - destination reached

Also, if d and prev and visited are all [3000], then you can't do for (i = 1; i <= n; ++i) . ARrays are indexed 0 to size-1.

Ah i found it!

Code:

if(route[i+2]==destination)
            {
                printf("\nDestination Reached\n");
                exit(EXIT_SUCCESS);
            }

route[i+2] should be route[i]. That solved my problem, THANKS A LOT GUYS!!