CODEWITHSUNDEEP
c++algorithmgraphdijkstra
echo
echo

Reputation: 86

Codewars:Path Finder #3: the Alpinist in C++

I just tried to finish a problem:Path Finder #3: the Alpinist in Codewars. I had passed all basic test cases and there were any errors under my own test cases. But when i submited my solution, my code failed for random test cased. My solution of problem is graph searching based Dijkstra algorithm and priority_queue. I think there my some potential errors i didn't consider. Please help me check it. I have tried achieve it for three hours.

My solution is below.

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int INF = 1e9;
const int WHITE = -1;
const int GRAY = 0;
const int BLACK = 1;
int path_finder(string maze)
{
    int result = 0;
    vector<pair<int, int>> element;
    vector<vector<pair<int, int>>> altitude;
    int width = (-1 + sqrt(5 + 4 * maze.size())) / 2;
    auto tem = maze.find('\n');
    while (tem != string::npos)
    {
        maze.erase(tem, 1);
        tem = maze.find('\n');
    }
    
    for (int i = 0; i < width; ++i)
    {
        for (int j = 0; j < width; ++j)
        {
            altitude.push_back(element);
            if (i >= 1)
                altitude[i * width + j].push_back(make_pair(i * width + j - width, abs(maze[i * width + j] - maze[i * width + j - width])));
            if (i < width - 1)
                altitude[i * width + j].push_back(make_pair(i * width + j + width, abs(maze[i * width + j] - maze[i * width + j + width])));
            if (j >= 1)
                altitude[i * width + j].push_back(make_pair(i * width + j - 1, abs(maze[i * width + j] - maze[i * width + j - 1])));
            if (j < width - 1)
                altitude[i * width + j].push_back(make_pair(i * width + j + 1, abs(maze[i * width + j] - maze[i * width + j + 1])));
        }
    }

    int* distance = new int[width * width];
    int* state = new int[width * width];
    for (int i = 0; i < width * width; ++i)
    {
        distance[i] = INF;
        state[i] = WHITE;
    }

    priority_queue<pair<int, int>> unfinished;
    unfinished.push(make_pair(0, 0));
    state[0] = GRAY;
    distance[0] = 0;
    while (!unfinished.empty())
    {
        pair<int, int> tem = unfinished.top();
        unfinished.pop();
        state[tem.second] = BLACK;

        if(distance[tem.second] < tem.first * (-1))
            continue;

        for (int i = 0; i < altitude[tem.second].size(); ++i)
        {
            if(state[altitude[tem.second][i].first] != BLACK)
            {
                unfinished.push(make_pair(-1 * altitude[tem.second][i].second, altitude[tem.second][i].first));
                if (distance[tem.second] + altitude[tem.second][i].second < distance[altitude[tem.second][i].first])
                {
                    distance[altitude[tem.second][i].first] = distance[tem.second] + altitude[tem.second][i].second;
                    state[altitude[tem.second][i].first] = GRAY;
                }
            }
        }
    }
    result = distance[width * width - 1];

    return result;
}

Upvotes: 0

Views: 270

Answers (1)

Christopher Miller
Christopher Miller

Reputation: 3461

Here is a test case where your code has the wrong answer.

"53072\n"

"09003\n"

"29977\n"

"31707\n"

"59844"

The least cost is 13, with this path:

{1 1 0 0 0}
{0 1 0 0 0}
{0 1 1 1 1}
{0 0 0 0 1}
{0 0 0 0 1}

But your program outputs 15.

Upvotes: 1

Related Questions