Flood fill by distance

Question

Say I have a grid with some obstacles:

 ----
|  X |
|    | 
|XX  |
|    |
 ----

I can fill this with numbers, as distance from the top left corner. But, because there are obstacles in the way some cells will take further to reach than a straight line:

 ----
|01X5|
|1234|
|XX45|
|7656|
 ----

This can be done through flood filling:

 ----   ----   ----   ----   ----   ----   ----   ---- 
|0 X | |01X | |01X | |01X | |01X | |01X5| |01X5| |01X5|
|    | |1   | |12  | |123 | |1234| |1234| |1234| |1234|
|XX  | |XX  | |XX  | |XX  | |XX4 | |XX45| |XX45| |XX45|
|    | |    | |    | |    | |    | |  5 | | 656| |7656|
 ----   ----   ----   ----   ----   ----   ----   ---- 

Your challenge is to, given a binary matrix containing obstacles, flood fill it like so from the top left hand corner and output a corresponding matrix.

The first example of a grid is equivalent to the following matrix:

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

And the corresponding output would be:

[ [0, 1, X, 5],
  [1, 2, 3, 4],
  [X, X, 4, 5],
  [7, 6, 5, 6] ]

Where X is any value that isn't a positive integer.

You may take any two consistent values in the matrix instead of 1 and 0, and you may choose any value to represent obstacles. Distances may be 0 or 1-indexed. You may assume the whole matrix can be flood filled from the top left corner, which cannot be an obstacle.

You must be able to support numbers with multiple digits.

This is code-golf, shortest wins!

Testcases

These use -1 as X.

[ [0, 0, 1, 0], [0, 0, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0] ] -> [ [0, 1, -1, 5], [1, 2, 3, 4], [-1, -1, 4, 5], [7, 6, 5, 6] ]
[ [0, 0, 0] ] -> [ [0, 1, 2] ]
[ [0, 1, 0, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0] ] -> [ [0, -1, 4, 5, 6, -1, 10], [1, 2, 3, -1, 7, 8, 9] ]

Answer 1

J, ⁵⁴ 46 bytes

[:(#-+/)](+[:+./(0,(,-)=0 1)|.!.0=&1)^:a:${.1:

Try it online!

Answer 2

BQN, 36 34 bytes^SBCS

Uses ∞ for obstacles in input and output.

{(𝕩⌈⊢⌊1+(«˘⌈«⌈»⌈»˘)⌾÷)⍟(≠⥊)0⌾⊑∞¨𝕩}

Run online!

0⌾⊑∞¨𝕩 Generate a matrix of the same shape as the input, with a 0 in the top left corner and ∞ anywhere else.
( ... )⍟(≠⥊) Iterate the function on the left as many times as there are values in the matrix. (You could get away with less iterations, but this is golfy)

(𝕩⌈⊢⌊1+(«˘⌈«⌈»⌈»˘)⌾÷) Tacit function that performs one step of flood filling:

( ... )⌾÷ Take the reciprocal of each value, do some transformations on that, then take the reciprocal (its own inverse) again.
The idea is that we want to shift in ∞ from each side, then take the element-wise minimum between the four matrices. BQN shift builtins » and « push in 0 instead, which is why do the shifting in "reciprocal space".
«˘⌈«⌈»⌈»˘ pushes in 0s from all four directions, and takes the element-wise maximum.

Now we increment each value (1+), take the minimum with the previous step (⊢⌊) and the maximum with the input (𝕩⌈) to make sure the obstacles stay at ∞.

---

An adjacency matrix based approach is much longer at 52 bytes:

↕∘≢{𝕩⌈+˝¬⊏˘>(𝕩=⌜˜⊸≥(+´|∘-)⌜˜𝕨)∨˝∘∧⎉1‿∞⍟(↕≠𝕩)≡⌜˜𝕨}⌾⥊⊢

Run online!

Answer 3

Jelly, 20 19 bytes

ẸŻạ§ỊẸʋƇ@ƬŒMŒṬ+C¬S:

Try it online!

Inspired by @Jonathan Allan's answer (it started as a golf of that answer, but portions were rewritten, and it changed so extensively that it makes more sense to post a new answer); this answer uses a similar algorithm (although not exactly the same).

Output is 1-based, using NaN for walls.

Explanation

ẸŻạ§ỊẸʋƇ@ƬŒMŒṬ+C¬S:
Ẹ                     1 if the input contains any nonzeros (it does)
 Ż                    prepend 0 (thus creating [0,1])
         Ƭ            Loop until we reach a steady state:
       Ƈ                {Set the loop variable to} a filtered subset of
        @ ŒM              the multidimensional indexes of {the input}
       Ƈ                keeping only those elements for which
      ʋ                   the following four-step procedure {returns true}:
  ạ                         absolute difference of {the index} from
                              {the loop variable, or each of its elements}
   §                        add the x-difference to the y-difference
     Ẹ                      at least one of those difference sums
    Ị                       has a magnitude of at most 1
            ŒṬ        {For each iteration}, create an array with 1s at
                         the indexes {in that iteration's loop variable}
              +       {For each iteration's array}, add, and reshape to,
               C        {the input} with each element subtracted from 1
                ¬     Replace 0s with 1s, other values with 0s
                 S    Sum {the arrays from each iteration}
                  :   Integer divide by {the input grid}

The basic idea is that we maintain a list of coordinates that our flood fill has reached, and repeatedly filter the list of non-wall coordinates to find those coordinates which are close to those in the previous iteration.

The initial coordinate, used on the first iteration, is [0,1]. Jelly uses 1-based indexing, so this is actually outside the array (but still at a distance of 1 from the top-left corner, allowing the loop to get started). The loop is written as a data-type polyglot; it works both on a single coordinate pair (such as [0,1]), and on a list of coordinate pairs (which is what it gets on every subsequent iteration). After the loop, the ŒṬ can treat the [0,1] the same way as all the coordinate lists (basically producing an array with no coordinates), so it doesn't matter that the loop variable is a coordinate pair on the first iteration and a list of coordinate pairs on subsequent iterations.

The +C doesn't have any effect on the array values (other than setting the value of walls to 1); its purpose is to pad out all the arrays generated by ŒṬ so that they're the same size as the input, making it possible to use ¬ to place 1s in all the squares that the flood-fill hadn't reached by that iteration. Then we can just sum the arrays to learn how long it took to reach each square, as in the other two Jelly answers.

Although Jelly has a constant Ø. to produce the list [0,1], writing it at the start of the program would trigger a special case in the parser, which would subsequently cause the ŒM later in the program to parse incorrectly. As a consequence, we need to generate the [0,1] as a function of the input, rather than using a constant, but fortunately this is possible in two bytes and thus the special case in question ends up not costing. (Because the input has a 1 in the top-left corner, there's guaranteed to be at least one nonzero value in the input.)

Answer 4

Jelly, 27 bytes

ŒM_Ø.ŒṬ»ḤZUµ4¡«³
FJỊṁ³ÇƬ¬S:

Try it online!

Input format: 0 for wall, 1 for passable cell.

Output format: 0-based, walls are represented as floating-point infinity.

This only works as a full program, because it assumes that the first command-line argument and the input to the main function are the same as each other (which they will be for a full program, but not for a function run as part of a larger program).

Explanation

Helper function 1Ŀ

The helper function takes a matrix of 1s and 0s as its input; everywhere that's a 0 in the program input must be a 0 in the helper function input, but otherwise the helper function can have 1s and 0s anywhere. The output from the helper function is the same matrix with every non-wall space (based on the input to the program as a whole) filled with a 1 if it was or was adjacent to a 1 in the helper function input, or 0 otherwise.

The basic algorithm is to double the value of every cell of the helper function input, and place a 1 to the left of every maximal-valued cell unless there was already a higher value there. Then we rotate our working value 90 degrees, and repeat a further three times. The values that were 1 in the helper function input will always be the maximal-valued cells (having been doubled more often than the cells we set to 1 during the helper function), so the four iterations set the cells to the left, beneath, to the right, and above them to positive values respectively (and then we're rotated back to the array's original orientation). Once we've done our placing of 1s to the left four times, we simply just maximum with the input to the program as a whole; this sets all the 1s, 2s, 4s, 8s, and 16s to 1, except for cells which were 0 in the program input which are set to 0, implementing the desired behaviour of the helper function.

ŒM_Ø.ŒṬ»ḤZUµ4¡«³
ŒM                 Indexes of maximal elements
  _Ø.              Subtract [0, 1] (i.e. the indexes to their left)
     ŒṬ            Create an array with 1s at only those indexes
       »           Take the maximum of that array and
        Ḥ            twice {the working value as of the start of this iteration}
         ZU        Transpose and flip (i.e. rotate 90°)
             ¡     Repeat
           µ         everything in this function so far
            4        4 times
              «    Take the {element-wise} minimum of that and
               ³     the first command-line argument to this program

Jelly helpfully handles the edge of the array for us – if ŒṬ sees a coordinate before the left edge of the array, it won't add it to the array it's creating. (However, it will nonetheless make use of the coordinate to know how many dimensions the array it's creating is meant to have, avoiding a crash if there are no indexes in range.)

Main program

Half the code in this is to create an array that's the same shape as the input array, but has a 1 in the top-left corner and 0s everywhere else (i.e. the location we're flood-filling from). Then, we run the helper function repeatedly to flood-fill, and convert the output to the desired format.

FJỊṁ³ÇƬ¬S:
F            Flatten the input array
 J           Create a list from 1 to the length {of the flattened array}
  Ị          Map 1 to 1, larger values to 0
   ṁ         Reshape back to the shape of the input
    ³        {no-op, fixes a parsing ambiguity by breaking up ṁÇ}
     Ç       Call the function 1Ŀ
      Ƭ        in a loop, until nothing changes, remember all results
       ¬     Swap 0s and 1s {in the list of outputs of 1Ŀ}
        S    Sum {for each cell, the number of iterations it was 0}
         :   Divide {cells by the corresponding input cell}

The basic idea is that a cell that should be 0 in the output has been 0 for no iterations of 1Ŀ calls; a cell that should be 1 in the output has been 0 for one iteration; a cell that should be 2 in the output has been 0 for two iterations, and so on (i.e. we can use the length of time the one-step floodfills took to reach a particular square to discover its distance from the starting point). So we can just count the number of iterations for which each cell was 0. In order to place non-integers in the cells which are walls in the input (these cells would "naturally" hold the largest value in the output plus 1), it's possible to use division with the input; for non-wall cells, this divides by 1 (a no-op), and for wall cells, this divides by 0 (returning floating-point infinity, which is not a positive integer). (: is normally integer division, so it returns an integer in most cases, but it returns floating-point infinity when dividing by 0.)

Answer 5

Retina, 121 bytes

^.
0

 
{P^` +\S+
(?<=(.)*) +_(?=(.*¶(?<-1>.)*(?(1)^))? +(\d+)|(?<=(?<3>\d+)((?(5)$)(?<-5>.)*¶.*)? +_(?=(.)*)))
 $.($3*__

Try it online! Uses _ for 0 and X for 1. Explanation:

^.
0

Start flood filling at the top left.

Space everything apart.

{`

Repeat until everything has been filled.

P^` +\S+

Align all of the columns to the largest value found so far.

(?<=(.)*) +_(?=(.*¶(?<-1>.)*(?(1)^))? +(\d+)|(?<=(?<3>\d+)((?(5)$)(?<-5>.)*¶.*)? +_(?=(.)*)))

Match underscores that are either to the left ( +_(?= +(\d+))), above ((?<=(.)*) +_(?=.*¶(?<-1>.)*(?(1)^) +(\d+)), to the right ( +_(?<=(?<3>\d+) +_)) or below ( +_(?<=(?<3>\d+)(?(5)$)(?<-5>.)*¶.* +_(?=(.)*))) an integer, ensuring to capture the integer in capture group 3.

 $.($3*__

Replace the underscore with the incremented integer.

Answer 6

JavaScript (Node.js), 114 bytes

Expects a matrix filled with \$0\$ and \$-1\$.

Outputs by updating the input matrix with 1-indexed distances.

f=(m,n=m[0][0]=1)=>m.map(q=(r,y)=>r.map((v,x)=>(h=d=>d+2?v|m[y+d--%2]?.[x+d%2]^n?h(d):r[x]=q=n+1:0)(2)))|q&&f(m,q)

Attempt This Online!

Commented

f = (                  // f is a recursive function taking:
  m,                   //   m[] = input matrix
  n =                  //   n = distance counter
  m[0][0] = 1          //   set m[0][0] to 1
) =>                   //
m.map(q =              // initialize q to a zero'ish value
(r, y) =>              // for each row r[] at position y in m[]:
  r.map((v, x) =>      //   for each value v at position x in r[]:
    ( h =              //     h is a recursive function taking
      d =>             //     a direction d
      d + 2 ?          //     if d is not equal to -2:
        v |            //       if v is already set
        m[y + d-- % 2] //       or the neighbor cell
        ?.[x + d % 2]  //       in direction d
        ^ n ?          //       is not equal to n:
          h(d)         //         try again with the next direction
        :              //       else:
          r[x] =       //         update the cell to n + 1
          q = n + 1    //         and set q to a non-zero value
      :                //     else:
        0              //       stop the recursion
    )(2)               //     initial call to h with d = 2
  )                    //   end of inner map()
)                      // end of outer map()
| q && f(m, q)         // if q was set, do a recursive call

Answer 7

Julia

97 bytes

h(X,r=1,c=1,d=0)=try d<X[r][c]&&(X[r][c]=d
for i=[5,7,1,3] h(X,r+i÷3-1,c+i%3-1,d+1)end)catch;end

Attempt This Online!

81 bytes

A greatly improved version provided by @MarcMush.

h(X,r=1,c=1,d=0)=d<get(X,(r,c),0)&&1:2:7 .|>i->h(X,r+i÷3-1,c+i%3-1,(X[r,c]=d)+1)

Attempt This Online!

representation:

• free slots -> Inf
• forbidden slots -> -Inf
• 0-based distance

Answer 8

Vyxal, 32 bytes

k₁w≬ƛ£?ÞT›'¥ε∑ṅ}ÞfU↔‹vÞǔ∑:fGε›*‹

Try it Online!

Port of Jonathan Allan's Jelly answer, byte count can certainly be way less.

Answer 9

Python3, 194 bytes:

def f(b):
 q=[(0,0,0)]
 while q:
  (x,y,v),*q=q
  for X,Y in[(0,1),(0,-1),(1,0),(-1,0)]:
   X+=x;Y+=y
   if-1<X<len(b)and-1<Y<len(b[0])and(X|Y)and 0==b[X][Y]:b[X][Y]=v+1;q+=[(X,Y,v+1)]
 return b

Try it online!

Answer 10

Jelly,  25  24 bytes

-1 using ais523's trick of using integer division to place inf as walls.

Ø1Wạ§ỊɗƇⱮẎQɗ@ƬŒMŒṬSFṀ_Ɗ:

A monadic Link that accepts the grid with 1 as space and 0 as wall and yields another grid containing the fill distances at spaces and inf at walls.

Try it online!

How?

Ø1Wạ§ỊɗƇⱮẎQɗ@ƬŒMŒṬSFṀ_Ɗ: - Link: Grid
Ø1                       - literal [1, 1]
  W                      - wrap -> [[1, 1]]
              ŒM         - maximal multidimensional indices of Grid -> space coordinates
             Ƭ           - start with A=[[1, 1]] and collect up while distinct applying:
            @            -   with swapped arguments:
           ɗ             -     last three links as a dyad - f(space coordinates, A):
        Ɱ                -       map (for a in A) with:
       Ƈ                 -         keep those (s in space-cordinates) for which:
      ɗ                  -           last three links as a dyad - f(s, a):
   ạ                     -             absolute difference
    §                    -             sums
     Ị                   -             insignificant? -> is s a neighbour of, or equal to, a?
         Ẏ               -       tighten -> flat list of neighbours
          Q              -       deduplicate
                ŒṬ       - multidimensional grids with 1s at those indices
                  S      - sum -> 0 at walls, 1 at furthest, 2 at next nearest, etc.
                      Ɗ  - last three links as a monad - f(X=that):
                   F     -   flatten
                    Ṁ    -   maximum -> value at top-left
                     _   -   subtract X (vectorises)
                       : - integer divide by the grid -> keeps space values, replaces wall with inf

Answer 11

JavaScript (Node.js), 110 bytes

a=>[,...0+a].map((_,i)=>a=a.map((r,y)=>r.map((c,x)=>x+y?c||i*[2,1,0,-1].some(k=>a[y+k%2]?.[x+--k%2]>0):1)))&&a

Attempt This Online!