Statistics

Problem Statement for "TheRectangularCityDiv2"

Problem Statement

John and Brus have found a nice horizontal plane and they built a rectangular city somewhere on the plane. The city has n rows and m columns of houses, with n*m ≤ 20. More precisely, John and Brus built a house at each lattice point (x, y) such that 0 ≤ x < n and 0 ≤ y < m.

Today is a holiday. John decided to go to the city and visit all the houses. However, some of the houses are locked since the owners left the city for the holiday. You are given a String[] city. For each x and y, the character city[x][y] represents the house at (x, y): '.' is an open house and '#' is a locked one.

John's trip has to satisfy the following constraints:
  • He has to visit each open house exactly once.
  • He cannot visit the locked houses and he cannot leave and re-enter the city during the trip.
  • His trip has to start somewhere on the border of the city. In other words, the first house he visits must have x = 0 or x = n-1 or y = 0 or y = m-1.
  • His trip also has to end somewhere on the border of the city.
  • From any house John may only move to an adjacent house. Two houses are adjacent if they are next to each other in the same row or column. Formally, (x1, y1) and (x2, y2) are adjacent if |x1 - x2| + |y1 - y2| = 1.
Brus now wants to compute the number of ways in which John can visit all the open houses in the city. Compute and return that number.

Definition

Class:
TheRectangularCityDiv2
Method:
find
Parameters:
String[]
Returns:
long
Method signature:
long find(String[] city)
(be sure your method is public)

Constraints

  • n will be between 1 and 20, inclusive.
  • m will be between 1 and 20, inclusive.
  • n*m will be between 1 and 20, inclusive.
  • city will contain exactly n elements.
  • Each element of city will consist of exactly m characters, each being either '.' or '#'.
  • At least one character in city will be '.'.

Examples

  1. { "....", ".##.", "...." }

    Returns: 20

    All houses on the city border have to be visited. John can start from any of them and choose the direction: either clockwise or counterclockwise. Thus the total number of ways to visit all open houses is 10 * 2 = 20;

  2. { "....", ".###", "...." }

    Returns: 2

    Now John has to start from one of the rightmost houses and then he has to travel around the city to the other rightmost house.

  3. { "....", "####", "...." }

    Returns: 0

    Here it's impossible to visit all opened houses.

  4. { "....", "....", "...." }

    Returns: 80

  5. {"."}

    Returns: 1

  6. {"........"}

    Returns: 2

  7. {".", ".", ".", ".", "."}

    Returns: 2

  8. {"..............."}

    Returns: 2

  9. {".."}

    Returns: 2

  10. {".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", ".", "."}

    Returns: 2

  11. {".##.........#."}

    Returns: 0

  12. {"...######.#."}

    Returns: 0

  13. {"..#.##.###..#."}

    Returns: 0

  14. {".", "#", ".", "#", ".", "#", "#", ".", "#"}

    Returns: 0

  15. {".#.#.###.###.#.."}

    Returns: 0

  16. {"...", "..."}

    Returns: 16

  17. {"...", "...", "..."}

    Returns: 24

  18. {"....", "....", "....", "...."}

    Returns: 296

  19. {"...", "...", "..."}

    Returns: 24

  20. {"..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 184

  21. {"...", "...", "...", "...", "..."}

    Returns: 132

  22. {"...", "...", "...", "..."}

    Returns: 80

  23. {"....", "....", "....", "....", "...."}

    Returns: 924

  24. {"......", "......"}

    Returns: 64

  25. {"...", "...", "..."}

    Returns: 24

  26. {".....", ".....", ".....", "....."}

    Returns: 924

  27. {"....", "....", "....", "....", "...."}

    Returns: 924

  28. {".##..", "....."}

    Returns: 4

  29. {"..", ".#", ".."}

    Returns: 2

  30. { "......", ".....#", "#....#" }

    Returns: 26

  31. {"#..", "...", "..."}

    Returns: 20

  32. {"..###", "..#..", "#....", "#...."}

    Returns: 8

  33. {"...##....", ".##....##"}

    Returns: 0

  34. { "...", ".##", "...", ".#.", "...", "..." }

    Returns: 0

  35. {"....", "#.#.", "#..."}

    Returns: 2

  36. {"....", "....", "..##", "####", "####"}

    Returns: 18

  37. {".....#", "######", "######"}

    Returns: 2

  38. {"####", "##..", "....", "....", "...."}

    Returns: 62

  39. {"...", "...", "..#", "###", "###", "###"}

    Returns: 14

  40. {"###", "###", "###", "#..", "...", "..."}

    Returns: 14

  41. {"####", "####", "####", "####", "###."}

    Returns: 1

  42. {"......", "......", ".....#"}

    Returns: 158

  43. {"####", "####", "####", "####", "##.."}

    Returns: 2

  44. {"....", ".##.", ".##.", ".##.", "...."}

    Returns: 28

  45. {"....", ".##.", ".##.", ".##.", "...."}

    Returns: 28

  46. {"####", "#..#", "#..#", "#..#", "####"}

    Returns: 0

  47. {"####", "#..#", "#..#", "#..#", "####"}

    Returns: 0

  48. {".....", ".....", ".....", "....." }

    Returns: 924

  49. {"....", "....", "...." }

    Returns: 80

  50. {"." }

    Returns: 1

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: