TopCoder WalkingHome – SRM 222 Div 1


https://community.topcoder.com/stat?c=problem_statement&pm=3444&rd=5868
    
Johnny has to walk home from school, and wants to map out the best route to take, so that he has to cross as few streets as possible.
You are given a String[] map that maps the roadway layout of Johnny's town. The location of Johnny's school is designated with a 'S' character, and the location of Johnny's home is designated with a 'H' character. North-South roads are denoted by a '|' character, while East-West roads are denoted by a '-' character. Intersections, which can never be crossed, are indicated by '*' characters. Fences, indicated by a 'F' character, can also never be crossed. All other areas are indicated by '.' characters; Johnny can walk freely over these areas.
For maximum safety, Johnny may only walk directly across a road, perpendicular to the traffic, never diagonally. All of Johnny's movements, onto and off of a road, and walking around town, should be in one of the four cardinal directions. Johnny may, however, cross roads that are multiple lanes wide, and doing so only counts as a single crossing. Two or more adjacent || characters are always considered to be a single road, and this works similarly for '-' characters that appear adjacent vertically.
For instance, the following requires only a single crossing, since it's a single two-lane road:
S.||.H
Also, a situation such as the following leaves Johnny with no safe way to walk home, since he cannot cross the road diagonally, and can only step onto and off a road in a direction perpendicular to the road:
S||
||H
Also notice that because Johnny can never move diagonally, in the following case, Johnny cannot get home:
S.F
.F.
F.H
You are to return an int indicating the fewest number of times Johnny must cross the street on his way home. If there is no safe way for Johnny to get home, return -1.
 

Definition

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

Notes

-If a street is more than one unit wide, it still only counts as a single crossing.
 

Constraints

-map will contain between 1 and 50 elements, inclusive.
-Each element of map will contain between 1 and 50 characters, inclusive.
-Each element of map will contain only the characters '.', '-', '|', '*', 'F', 'S', 'H'.
-There will be exactly one occurrence each of 'S' and 'H' in map.
-Each element of map will contain the same number of characters.
 

Examples

0)
    
{"S.|..",
 "..|.H"}
Returns: 1
Here, Johnny lives right across the street from the school, so inevitably, he's crossing the street once to get home.
1)
    
{"S.|..",
 "..|.H",
 "..|..",
 "....."}
Returns: 0
Similar to above, but since the road has a dead end (maybe even a cul-de-sac at the end), Johnny can get home without actually having to cross the road.
2)
    
{"S.||...",
 "..||...",
 "..||...",
 "..||..H"}
Returns: 1
Notice here that even though it's a 2-lane highway, it only counts as a single crossing.

https://github.com/livingstonese/topcoder/blob/master/src/main/java/srm222/division1/WalkingHome.java
https://github.com/rdiachenko/black-box/blob/master/topcoder/java/com/github/rd/blackbox/topcoder/WalkingHome.java
public int fewestCrossings(String[] map) {
  int n = map.length;
  int m = map[0].length();
  char[][] field = new char[n][m];
  int[] source = new int[2];
  int[] target = new int[2];
  init(map, field, source, target);

  int[][] queue = new int[n * m * 10][2];
  int[][] crossings = initCrossings(n, m);
  int head = 0;
  int tail = 1;
  queue[head][X] = source[X];
  queue[head][Y] = source[Y];
  crossings[source[X]][source[Y]] = 0;

  while (tail > head) {
    int i = queue[head][X];
    int j = queue[head][Y];
    int currentCrossings = crossings[i][j];
    ++head;

    for (int[] next : getNeighbours(i, j, field, n, m)) {
      int cost = ((field[i][j] == '.' || field[i][j] == 'S')
          && (field[next[X]][next[Y]] == '-' || field[next[X]][next[Y]] == '|')) ? 1 : 0;
      int nextCrossings = crossings[next[X]][next[Y]];

      if (nextCrossings == -1 || nextCrossings > currentCrossings + cost) {
        queue[tail][X] = next[X];
        queue[tail][Y] = next[Y];
        crossings[next[X]][next[Y]] = currentCrossings + cost;
        ++tail;
      }
    }
  }
  return crossings[target[X]][target[Y]];
}

private void init(String[] map, char[][] field, int[] source, int[] target) {
  for (int i = 0; i < map.length; i++) {
    for (int j = 0; j < map[0].length(); j++) {
      field[i][j] = map[i].charAt(j);

      if (field[i][j] == 'S') {
        source[X] = i;
        source[Y] = j;
      } else if (field[i][j] == 'H') {
        target[X] = i;
        target[Y] = j;
      }
    }
  }
}

private int[][] initCrossings(int n, int m) {
  int[][] visited = new int[n][m];

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      visited[i][j] = -1;
    }
  }
  return visited;
}

private List<int[]> getNeighbours(int i, int j, char[][] field, int n, int m) {
  int[] is = { -1, 0, 1, 0 };
  int[] js = { 0, 1, 0, -1 };
  List<int[]> neighbours = new ArrayList<>();

  for (int k = 0; k < is.length; k++) {
    int nexti = i + is[k];
    int nextj = j + js[k];

    if (isValid(is[k] == 0, i, j, nexti, nextj, field, n, m)) {
      neighbours.add(new int[] { nexti, nextj });
    }
  }
  return neighbours;
}

private boolean isValid(boolean horizontal, int i, int j, int nexti, int nextj, char[][] field, int n, int m) {
  return nexti >= 0 && nexti < n
      && nextj >= 0 && nextj < m
      && field[nexti][nextj] != 'F'
      && field[nexti][nextj] != '*'
      && ((horizontal && field[i][j] != '-' && field[nexti][nextj] != '-')
      || (!horizontal && field[i][j] != '|' && field[nexti][nextj] != '|'));
}



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