Statistics

Problem Statement for "TheRectangularCityDiv1"

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 ≤ 100. 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:
TheRectangularCityDiv1
Method:
find
Parameters:
String[]
Returns:
long
Method signature:
long find(String[] city)
(be sure your method is public)

Notes

  • You may assume that for any valid input the correct return value fits into a long.

Constraints

  • n will be between 1 and 100, inclusive.
  • m will be between 1 and 100, inclusive.
  • n*m will be between 1 and 100, 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 of travel: 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 two rightmost houses and travel around the city to the other rightmost house.

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

    Returns: 0

    Here it's impossible to visit all open 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: 0

  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: 2

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

    Returns: 2

  50. {"......................."}

    Returns: 2

  51. {".", "#", "#", ".", ".", ".", ".", ".", ".", ".", ".", ".", "#", ".", ".", ".", "#", ".", ".", ".", "#", "#", "#", "#", "#", "#", ".", "#", ".", ".", ".", ".", ".", ".", "#", ".", "#", "#", ".", "#", "#", "#", ".", ".", "#", ".", ".", ".", "#", ".", "#", ".", "#", ".", "#", "#", "."}

    Returns: 0

  52. {"..#.#.###.###.#....##...###..####.##.###..###...#...##.#"}

    Returns: 0

  53. {".#..##........#..#..###.##.#..#..#.#.#.#####.#..###.....#.#..#.#.#......##..###"}

    Returns: 0

  54. {".", ".", "#", ".", "#", "#", "#", "#", "#", "#", "#", "#", ".", "#", ".", ".", "#", ".", "#", "#", "#", ".", ".", "#", ".", "#", ".", ".", "#", "#", ".", ".", "#", "#", ".", "#", "#", "#", ".", "#", "#", "#", "#", "#", "#", "#", ".", ".", ".", ".", ".", "#", "#", "#", "#", "#", "#", ".", "#", ".", ".", ".", ".", "."}

    Returns: 0

  55. {"..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 3616

  56. {"..........................", ".........................."}

    Returns: 1304

  57. {"..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 2668

  58. {"..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 2816

  59. {"..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 268

  60. {"..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 4904

  61. {"...", "...", "...", "...", "...", "...", "...", "...", "...", "...", "...", "...", "...", "...", "...", "...", "..."}

    Returns: 793344

  62. {"............", "............", "............", "............", "............", "............", "............"}

    Returns: 460310200136

  63. {"..............................", ".............................."}

    Returns: 1744

  64. {"..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 1744

  65. {"..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", "..", ".."}

    Returns: 1516

  66. {"..........", "..........", "..........", "..........", "..........", "..........", "..........", "..........", "..........", ".........."}

    Returns: 153925448694216

  67. {"...........", "...........", "...........", "...........", "...........", "...........", "...........", "...........", "..........."}

    Returns: 80716343118872

  68. {".........", ".........", ".........", ".........", ".........", ".........", ".........", ".........", ".........", ".........", "........."}

    Returns: 80716343118872

  69. {"..........", "..........", ".#........", "..........", ".........#", "..........", "...#......", "..........", ".......#..", ".#......#."}

    Returns: 0

  70. {"..............", "..............", "..............", ".............#", ".#............", "..............", ".......#......"}

    Returns: 52636824

  71. {"....#.#", "#.#.#..", ".......", "..#.#..", ".#.....", ".......", ".......", ".......", ".......", ".#.....", ".......", ".....#.", ".......", "......."}

    Returns: 0

  72. {".........", ".........", ".........", "#........", ".........", ".........", "......#..", ".......#.", "..#......", ".........", "........."}

    Returns: 315892808

  73. {"...........", "...........", "...........", "...........", "...........", "...........", "...........", "........###", "###########"}

    Returns: 125113936572

  74. {"##########", "##########", "##########", "##########", "#########.", "..........", "..........", "..........", "..........", ".........."}

    Returns: 922034

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: