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

Unique Binary Search Trees

/*** Given  n , how many structurally unique  BST's  (binary search trees) that store values 1... n ? For example, Given  n  = 3, there are a total of 5 unique BST's.    1         3     3      2      1     \       /     /      / \      \      3     2     1      1   3      2     /     /       \                 \    2     1         2         ...
Read more

Sudoku

/*** Sudoku Given a partially filled 9×9 2D array ‘grid[9][9]‘, the goal is to assign digits (from 1 to 9) to the empty cells so that every row,   column, and subgrid of size 3×3 contains exactly one instance of the digits from 1 to 9. Backtracking Algorithm Like all other Backtracking problems, we can solve Sudoku by one by one assigning numbers to empty cells.  Before assigning a number, we check whether it is safe to assign. We basically check that the same number  is not present in current row, current column and current 3X3 subgrid. After checking for safety,  we assign the number, and recursively check whether this assignment leads to a solution or not.  If the assignment doesn’t lead to a solution, then we try next number for current empty cell.  And if none of number (1 to 9) lead to solution, we return false. ***/ #include <iostream> using namespace std; class Sudoku { public :      ...
Read more