Topcoder RevolvingDoors – SRM 223 Div 1


https://community.topcoder.com/stat?c=problem_statement&pm=3064&rd=5869
https://github.com/keshavnandan/Topcoder/blob/master/RevolvingDoors.txt
You are in a maze containing revolving doors. The doors can be turned 90 degrees by pushing against them in either direction. You are to find a route from the start square to the end square that involves revolving as few doors as possible. Given a map of the maze, determine the fewest number of door revolutions necessary to get from the start to the end.
In the map:
   ' ': empty space
   '#': wall
   'O': center of a revolving door (letter "oh", not zero)
   '-': horizontal door (always adjacent to a 'O')
   '|': vertical door (always adjacent to a 'O')
   'S': start square
   'E': end square
Each revolving door will always be oriented horizontally (with two horizontal segments) or vertically (with two vertical segments):
    |
    O  or  -O-
    |
Doors can be revolved 90 degrees by moving onto a door segment from any of the 4 squares diagonally adjacent to the door center, i.e., the 'X' characters below:
   X|X     X X
    O  or  -O-
   X|X     X X
Here is an example map:
        ###
        #E#
       ## #
    ####  ##
    # S -O-#
    # ###  #
    #      #
    ########
In this example, 2 door revolutions are necessary to get from 'S' to 'E'. The first turn is shown here:
        ###         ###
        #E#         #E#
       ## #        ## #
    ####  ##    #### |##
    # S -O-#    # S  OX#
    # ### X#    # ###| #
    #      #    #      #
    ########    ########
And the second turn is shown here:
        ###         ###
        #E#         #E#
       ## #        ## #
    ####X|##    #### X##
    # S  O #    # S -O-#
    # ###| #    # ###  #
    #      #    #      #
    ########    ########
Your method should return an int, the minimum number of door revolutions necessary to get from the start square to the end square. If there is no way to reach the end square, return -1.
 

Definition

    
Class:RevolvingDoors
Method:turns
Parameters:String[]
Returns:int
Method signature:int turns(String[] map)
(be sure your method is public)
    
 

Notes

-Assume that all squares off the edge of the map are walls.
 

Constraints

-map will contain between 3 and 50 elements, inclusive.
-Each element of map will contain between 3 and 50 characters, inclusive.
-Each element of map will contain the same number of characters.
-Each character in map will be one of 'S', 'E', 'O', '-', '|', '#', and ' ' (space).
-There will be exactly one 'S' and one 'E' in map.
-There will be between 1 and 10 doors, inclusive, and they will be formatted in map as described in the problem statement.
-No two doors will be close enough for any part of them to occupy the same square.
-It is not allowed for a door to be blocked and unable to turn. There will not be any walls in any of the 4 squares immediately adjacent to the center of a door, nor will a door be on the edge of the map.
 

Examples

0)
    
{ "    ### ",
  "    #E# ",
  "   ## # ",
  "####  ##",
  "# S -O-#",
  "# ###  #",
  "#      #",
  "########" }
Returns: 2
This is the example from the problem statement.
1)
    
{ "#### ",
  "#S|##",
  "# O #",
  "##|E#",
  " ####" }
Returns: -1
There is no way to reach the end square.
2)
    
{ " |  |  |     |  |  |  |  |  | ",
  " O  O EO -O- O  O  O  O  OS O ",
  " |  |  |     |  |  |  |  |  | " }
Returns: 7
The optimal path involves turning the 3rd door twice, and the 5th, 6th, 7th, 8th, and 9th doors once each (counting from the left). Note that the 'S' and 'E' do not block doors, and in fact you must turn the 3rd door twice to end up on the 'E'.
3)
    
{ "###########",
  "#    #    #",
  "#  S | E  #",
  "#    O    #",
  "#    |    #",
  "#         #",
  "###########" }
Returns: 0
4)
    
{ "        E",
  "    |    ",
  "    O    ",
  "    |    ",
  " -O-S-O- ",
  "    |    ",
  "    O    ",
  "    |    ",
  "         " }
Returns: -1
You are stuck, unable to move or turn any doors from this position.
5)
    
{ "##E#   ",
  "#  ##  ",
  " -O-## ",
  " #  ## ",
  " ##  ##",
  "  -O-  ",
  "##  ## ",
  " # ### ",
  " #  S  " }
Returns: 5
6)
    
{ "#############",
  "#  #|##|#   #",
  "#   O  O    #",
  "# E || || S #",
  "#    O  O   #",
  "#   #|##|#  #",
  "#############" }
Returns: 4
After all the doors have been turned, the map looks like this:
    #############
    #  # ## #   #
    #  -O--O-   #
    # E       S #
    #   -O--O-  #
    #   # ## #  #
    #############

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.


https://www.xuebuyuan.com/zh-tw/1126297.html?mobile=0
感覺這道題比前兩道應用BFS演算法的題目要難一些,不像之前的那麼直接,如果這道題目要求的是最短的頻數的話,那跟前兩道就差不多了,但這裡求的是最少旋轉門的次數,這就有點複雜了,我的思路如下:
1. 判斷當前位置是否是終點,不是則搜索由當前位置可以到達的旋轉門,並將旋轉之後的結果狀態存入LD鏈表尾。
2. 從LD鏈表中取出第一個元素作為當前狀態,重複步驟1.
遇到的問題:BFS演算法需要設置一個訪問狀態標誌,要不然會發生重複搜索同一個狀態的情況,開始的時候我只是設置了一個visited數組確定搜索可到達的旋轉門的過程不會出現重複搜索的過程,結果出現了大問題,因為搜索過程中,進入LD中的元素會有重複的,所以會進行大量的重複搜索,時間複雜度大大增加,而且遇到某些地圖還會出現無限循環的情況,如地圖示例1,而地圖示例2直接就是算半天算不出來,後來我增加了一個 isVisited函數確保進入LD的元素跟以前進入過的元素沒有重複,問題才解決了。


還有一個要注意的問題就是地圖示例的情況不是旋轉6次,而是7次,最後一次也要先旋轉門才能到達終點,開始的程序少算了這一步。


https://github.com/keshavnandan/Topcoder/blob/master/RevolvingDoors.cpp
https://github.com/livingstonese/topcoder/blob/master/src/main/java/srm223/divsion1/RevolvingDoors.java


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