Wizard

There are 10 wizards, 0-9, you are given a list that each entry is a list of wizards known by wizard. Define the cost between wizards and wizard as square of different of i and j. To find the min cost between 0 and 9.
For example:
wizard[0] list: 1, 4, 5
wizard[4] list: 9
wizard 0 to 9 min distance is (0-4)^2+(4-9)^2=41 (wizard[0]->wizard[4]->wizard[9])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#pragma once

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

namespace airbnb
{
    class Wizard
    {
    public:
        vector<int> GetMinCostPath(vector<vector<int>>& wizards, int start, int end, int n)
        {
            vector<int> minPath;
            vector<int> parents(n, -1);
            vector<int> cost(n, INT_MAX);

            queue<int> wq;
            wq.push(0);
            cost[0] = 0;

            while (!wq.empty())
            {
                auto cur = wq.front();
                wq.pop();

                for (auto neigb : wizards[cur])
                {
                    int cur_cost = cost[cur] + pow(abs(neigb - cur), 2);
                    if (cur_cost < cost[neigb])
                    {
                        wq.push(neigb);
                        cost[neigb] = cur_cost;
                        parents[neigb] = cur;
                    }
                }
            }

            if (cost[end] == INT_MAX)
            {
                return minPath;
            }

            int node = end;
            while (node != -1)
            {
                minPath.insert(minPath.begin(), node);
                node = parents[node];
            }

            for (int i = 0; i < n; i++)
            {
                cout << i << ". cost: " << cost[i] << ", parents: " << parents[i] << endl;
            }

            return minPath;
        }
    };
}

Comments

Post a Comment

Popular posts from this blog

Backtracking Algorithm

Backtracking  is a general  algorithm  for finding all (or some) solutions to some  computational problem , that incrementally builds candidates to the solutions, and abandons each partial candidate  c  ("backtracks") as soon as it determines that  c  cannot possibly be completed to a valid solution. Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than  brute force enumeration  of all complete candidates , since it can eliminate a large number of candidates with a single test. Backtracking is an important tool for solving  constraint satisfaction problems , such as  crosswords ,  verbal arithmetic , Sudoku , and many other puzzles. It is often the most convenient (if n
Read more