SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Problem
  2. You have been hired recently as the Chief Decision Maker (CDM) at a famous parcel delivery company, congratulations! Customers love speedy deliveries of their parcels and you have decided to decrease the time it takes to deliver parcels around the world to win customers. You have introduced this idea to the authorities and they have allocated you enough budget to build at most one new delivery office.
  3.  
  4. The world can be divided into an R × C grid of squares. Each square either contains a delivery office or it does not. You may pick a grid square that does not already contain a delivery office and build a new delivery office there.
  5.  
  6. The delivery time of a parcel to a square is 0 if that square contains a delivery office. Otherwise, it is defined as the minimum Manhattan distance between that square and any other square containing a delivery office. The overall delivery time is the maximum of delivery times of all the squares. What is the minimum overall delivery time you can obtain by building at most one new delivery office?
  7.  
  8. Note: The Manhattan distance between two squares (r1,c1) and (r2,c2) is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the absolute value.
  9.  
  10. Input
  11. The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case contains the number of rows R and number of columns C of the grid. Each of the next R lines contains a string of C characters chosen from the set {0, 1}, where 0 denotes the absence of a delivery office and 1 denotes the presence of a delivery office in the square.
  12.  
  13. Output
  14. For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum overall delivery time you can obtain after adding at most one additional delivery office.
  15.  
  16. Limits
  17. Time limit: 15 seconds per test set.
  18. Memory limit: 1GB.
  19. 1 ≤ T ≤ 100.
  20. There is at least one delivery office in the initial grid.
  21.  
  22. Test set 1 (Visible)
  23. 1 ≤ R ≤ 10.
  24. 1 ≤ C ≤ 10.
  25.  
  26. Test set 2 (Hidden)
  27. 1 ≤ R ≤ 250.
  28. 1 ≤ C ≤ 250.
  29.  
  30. Sample
  31.  
  32. Input
  33.    
  34.  
  35.  
  36. 3
  37. 3 3
  38. 101
  39. 000
  40. 101
  41. 1 2
  42. 11
  43. 5 5
  44. 10001
  45. 00000
  46. 00000
  47. 00000
  48. 10001
  49.  
  50.   OUTPUT
  51. Case #1: 1
  52. Case #2: 0
  53. Case #3: 2
  54.  
  55.  
  56. In Sample Case #1, you get a minimum overall delivery time of 1 by building a new delivery office in any one of the five squares without a delivery office.
  57.  
  58. In Sample Case #2, all the squares already have a delivery office and so the minimum overall delivery time is 0. Note you have to add at most one delivery office.
  59.  
  60. In Sample Case #3, to get a minimum overall delivery time of 2, you can build a new delivery office in any of these squares: (2, 3), (3, 2), (3, 3), (3, 4), or (4, 3). Any other possibility results in a higher overall delivery time than 2.
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top