why the answer is 13 in the example?


  • 0
    J

    I am very confused about this question.
    Input: grid =
    [[1,1,1,0,0,0,0,0,0],
    [1,0,1,0,1,1,1,1,1],
    [1,1,1,0,0,0,0,0,0]]
    Output: 13
    Explanation: The region on the left only builds two new walls.

    it should be 12, the 0 at (1, 3) will be always infected.

    we build 10 walls(up and down, left is not needed) for the region on the right, after one night it becomes:
    111100000
    111111111
    111100000
    the second day, build 2 walls is enough.

    Total is 10 + 2 = 12


  • 0
    J

  • 1
    R

    [[1,1,1,0,X,X,X,X,X],
    [1,0,1,X,1,1,1,1,1],
    [1,1,1,0,X,X,X,X,X]]
    I think it takes 11 walls for the right region (maybe you missed [1,3])

    Then it takes two as X, so total are 13.
    [[1,1,1,1,X,0,0,0,0],
    [1,1,1,1,1,1,1,1,1],
    [1,1,1,1,X,0,0,0,0]]

    correct?


  • 0
    I

    I don't get the requirements of the problem.
    what if in this example, on 1st day we just build 4 walls surrounding the left 0, and that would save the day wouldn't it? if so the expected result should be 4?


  • 0
    J

    we don't need to protect (1, 3), it will be infected by the left side.

    @r97922153-gmail.com


  • 0
    R

    [[1,1,1,X,0,0,0,0,0],
    [1,X,1,X,1,1,1,1,1],
    [1,1,1,X,0,0,0,0,0]]

    I guess if you start from left, at the 1st step, 7 walls are built.

    [[1,1,1,X,1,1,1,1,1],
    [1,-,1,1,1,1,1,1,1],
    [1,1,1,X,1,1,1,1,1]]

    Then 4 walls are built.
    Notice that, ex for the top X is spent 2 walls by preventing virus from right & down. Totally it costs 11.

    However, it only saves 3 grids.
    Compared to the case if you start from right, you can save 8 grid.

    Hence I guess:

    1. You need to save at most grids as you can.
    2. If there is a tie, select the case where less walls are built.

    Correct?


  • 0
    J

    @r97922153-gmail.com

    if we start from left, 10 is enough.

    similarly we don't need to protect (1, 3)


  • 0
    R

    @jordandong

    I think the rule is once you decide to protect a region, you MUST make all the walls which are adjacent to it. Instead of ignoring some of them.

    I think it is ambiguous in description but from examples you can deduce to it.

    " A wall (and only one wall) can be installed between any two 4-directionally adjacent cells..."


  • 0
    F

    remember you can build only 2 walls per try:
    [
    [1, 1, 1, 0, 0, 0, 0, 0, 0]
    [1, 0, 1, 0, 1, 1, 1, 1, 1]
    [1, 1, 1, 0, 0, 0, 0, 0, 0]
    ]

    becames

    [1, 1, 1, 1, 2, 2, 2, 2, 2]
    [1, 1, 1, 1, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 2, 2, 2, 2, 2]

    after the first iteration, then you can build only [0, 4] and [2, 4]


  • 0
    R

    @r97922153-gmail.com
    The description is pretty ambiguous.
    " A wall (and only one wall) can be installed between any two 4-directionally adjacent cells..."
    Does this mean walls have to installed between all two 4-directionally adjacent cells?
    I think @jordandong is correct.
    If one cell will be infected anyway, why do we waste one wall to protect it??
    Can the author describe the problem more clear?
    @administrators @yujiehuang @awice


  • 0
    S
    This post is deleted!

  • 0
    J

    not sure what u r talking about? Did you read the problem and understand what the problem require?

    @sundyli


  • 0
    S
    This post is deleted!

  • 1
    A

    As per my understanding of the problem after multiple reads, the reason for 13 is as below:

    Starting day:
    [[1,1,1,0,0,0,0,0,0],
    [1,0,1,0,1,1,1,1,1],
    [1,1,1,0,0,0,0,0,0]]

    First day wall setup
    [[1,1,1,0,0,0,0,0,0],
    _______-, - ,-, -, -
    [1,0,1,0 -1,1,1,1,1],
    _______
    -, -, -, -, -

    [1,1,1,0,0,0,0,0,0]]

    I did not quite understanding as to why people use Xs on 0s to describe a wall block as it is confusing. The wall is installed on the boundary between 4 adjacent cells of one region per day. So there are 11 walls here (represented by small hyphens '- ') around one region.

    Second day situation after infection:
    [[1,1,1,1,0,0,0,0,0],
    _______-, -, -, -, -
    [1,1,1,1 -1,1,1,1,1],
    _______
    -, -, -, -, -

    [1,1,1,1,0,0,0,0,0]]

    Note that: (1,3) (0 style indexing) is affected by (1,2) the previous night though we blocked (1,4) from attacking.

    Second day wall setup:
    [[1,1,1,1 - 0,0,0,0,0],
    ________-, -, -, -, -
    [1,1,1,1 - 1,1,1,1,1],
    _______ -, -, -, -, -
    [1,1,1,1 - 0,0,0,0,0]]

    2 more walls are installed (the entire left side of 1s is one region and that is why we can install both the walls). This makes it 13.

    Hope this helps.


  • 0
    B

    The example implies that we should be building a wall around an entire region even if the adjacent 0 will be affected by another region.

    for example if we had
    [[1,0,1],
    [1.0.1],
    [1,0,1]]

    the answer would be 3 not 0. even though all 0's will be affected by the next day!


  • 0
    A

    @Badakhms I am not sure but I think the answer is 6 and not 3. 3 walls between the 1s on the left and zeros and 3 walls on the right between the zeros and the 1s on the right.


  • 0
    B

    @arunvishwanathan88
    Day one, 3 walls.
    Either left or right region. They only protect cells from being affected by the side you build the wall.
    Day two, 0 wall
    The all three zeros are already contaminated, thus no wall need to be built any more. So the final answer is 3.

    It's a bit tricky.


  • 0
    A

    @ben.meng.7 my bad! I just forgot that only one region can be contained per day. Yes it is 3 due to that.


  • 0
    T

    The answer is write, but explanation is confusing at best. The largest region which will get affected should be protected first, which means 11 walls to isolate right virus region. By next day virus from left is spread to 4th column, so we need 2 more walls to protect from that making total to 13.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.