CaptureThemAll – TopCoder SRM 207 Div 2


https://community.topcoder.com/stat?c=problem_statement&pm=2915&rd=5853
    Harry is playing magical chess. In this version of the game, all pieces move the same way as in regular chess, but players can cast some magical spells. Unfortunately, Harry's opponent, Joe, has captured all of Harry's pieces except one knight; Joe, on the other hand, still has a queen and a rook. The only chance Harry has to win this game is to cast a spell, "Haste", that will allow Harry's knight to make several moves in a row. You should determine the minimal number of moves the knight needs to capture both the rook and the queen, assuming neither of them moves. You may capture them in either order - rook first or queen first.



You will be given a String, knight, containing information about the knight. You will also be given a String, queen, and a String, rook, giving you information about Joe's pieces. knightrook and queen will be formatted as "cr", where c is a character between 'a' and 'h', inclusive, determining the column on the board ('a' is the first column, 'h' is the last), and r is a digit between '1' and '8', inclusive, determining the row (1 is the lowest, 8 is the highest).

Definition

    
Class:CaptureThemAll
Method:fastKnight
Parameters:String, String, String
Returns:int
Method signature:int fastKnight(String knight, String rook, String queen)
(be sure your method is public)
    

Notes

-A knight's jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if knight is in the (0,0) now, it can be in (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2) after his move.
-The knight will capture one of Joe's pieces if it ends its move in the cell that the piece occupies.
-The knight cannot jump out of the board.
-A chessboard has 8 rows and 8 columns.

Constraints

-knightrook and queen will all be distinct.
-knightrook and queen will be formatted as "cr", where c is a lowercase character between 'a' and 'h', inclusive, and r is a digit between '1' and '8', inclusive.

Examples

0)
    
"a1"
"b3"
"c5"
Returns: 2
From "a1", the knight can move directly to "b3" and capture the rook. From there, the knight can move directly to "c5" and capture the queen.
1)
    
"b1"
"c3"
"a3"
Returns: 3
The rook and the queen are both 1 move away from the knight. Once the knight captures one of them (it doesn't matter which one), it can return to its starting location, and capture the other piece in one more move.
2)
    
"a1"
"a2"
"b2"
Returns: 6
The rook and the queen are close, but it takes 6 moves to capture them.

https://github.com/salman-awan/topcoder-srm-solutions/blob/master/SRM%20207/CaptureThemAll.h
    int fastKnight(string knight, string rook, string queen)
    {
        // get initial positions of knight, rook and queen
        auto knight_pos = Position(knight[1] - '1', knight[0] - 'a');
        auto rook_pos = Position(rook[1] - '1', rook[0] - 'a');
        auto queen_pos = Position(queen[1] - '1', queen[0] - 'a');

        // get shortest path from knight -> rook -> queen
        int path1 = shortestPath(knight_pos, rook_pos) + shortestPath(rook_pos, queen_pos);

        // get shortest path from knight -> queen -> rook
        int path2 = shortestPath(knight_pos, queen_pos) + shortestPath(queen_pos, rook_pos);

        // return the minimum of path1 and path2
        return min(path1, path2);
    }

private:
    // returns the shortest path length from the knight start position to the knight end position using BFS
    int shortestPath(const Position& start, const Position& end)
    {
        // maintain a set of all visited positions
        set<Position> visited;

        // maintain a queue of all positions that we need to visit
        // the queue will store a std::pair to capture the shortest path lengths
        // for each position starting from the start position
        queue<pair<Position, int>> q;

        // add the start position to the queue to get started
        q.push(make_pair(start, 0));

        while (!q.empty())
        {
            // pop next position in the queue
            auto cur = q.front();
            q.pop();

            // add this position to the set of visited positions
            visited.insert(cur.first);

            // if we have reached the end position, return the shortest path length for this position
            if (cur.first == end)
                return cur.second;

            // otherwise get all valid knight moves from this position
            auto moves = moveKnight(cur.first);

            // push these knight moves into the queue if we have not visited those positions before
            // their shortest path length will be +1 the current shortest path length
            for (auto m : moves)
            {
                if (visited.find(m) == visited.end())
                    q.push(make_pair(m, cur.second + 1));
            }
        }

        // just a fail-safe to return an arbitrarily large value (in terms of chess board moves)
        return 64;
    }
https://github.com/smalex-als/smalex-at-topcoder/blob/master/src/p200/srm207/CaptureThemAll.java
public int fastKnight(String knight, String rook, String queen) {
    int[] coorsKnight = toCoords(knight);
    int[] coorsRook = toCoords(rook);
    int[] coorsQueen = toCoords(queen);
    int[][] delta = new int[][]{
            {-2, -1},
            {-2, 1},
            {2, -1},
            {2, 1},
            {-1, -2},
            {1, -2},
            {-1, 2},
            {1, 2}
    };

    return Math.min(
            countStep(coorsKnight, coorsRook, delta) + countStep(coorsRook, coorsQueen, delta),
            countStep(coorsKnight, coorsQueen, delta) + countStep(coorsQueen, coorsRook, delta));
}

http://algoexplained.blogspot.com/2016/12/capturethemall-topcoder.html
public int fastKnight(String knight, String rook, String queen) {
boolean[][] joe = new boolean[8][8];
<8 i="" p=""><8 j="" p=""> 
int hx = Integer.valueOf(knight.substring(1))-1;
int hy = knight.charAt(0) - 'a';
joe[Integer.valueOf(rook.substring(1))-1][rook.charAt(0) - 'a'] = true;
joe[Integer.valueOf(queen.substring(1))-1][queen.charAt(0) - 'a'] = true;

LinkedList queue = new LinkedList();
queue.add(new Harry(hx,hy,0));
int[] captured = new int[4];

while (queue.size() > 0) {
Harry current = queue.removeFirst();
if (capture(current, joe, captured)) {
if (captured[0] != 1) {
captured[0] = 1;
captured[1] = current.move;
queue.clear();
queue.add(new Harry(current.x,current.y,current.move));
} else {
captured[2] = 1;
captured[3] = current.move;
}

}
if (captured[0] == 1 && captured[2] == 1)
return current.move;
addNeighbors(queue, current);
}

return -1;
}

public boolean capture(Harry harry, boolean[][] joe, int[] captured) {
if (joe[harry.x][harry.y]){
// only capture one in the same neighbors
if (!(captured[0] == 1 && captured[1] == harry.move)) {
joe[harry.x][harry.y] = false;
return true;
}
}

return false;
}

public void addNeighbors(LinkedList queue, Harry current) {
int[] dx = {-2,-2,2,2,-1,1,-1,1};
int[] dy = {-1,1,-1,1,-2,-2,2,2};
for (int i=0;i<8 i="" p=""> int x = current.x + dx[i];
int y = current.y + dy[i];
if (x >=0 && y >= 0 && x < 8 && y <8 br=""> queue.add(new Harry(x,y,current.move + 1));
}
}
}

class Harry{
int x;
int y;
int move;
public Harry(int xx, int yy, int m) {
x = xx;
y = yy;
move = m;
}
}


Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts