Skip to main content
12 of 15
fixed a bug
Arnauld
  • 197.7k
  • 20
  • 179
  • 650

#JavaScript (ES6),  228  195 bytes

Expects a matrix of characters as input.

This can be quite slow on some inputs, such as the last test case.

m=>m.map((r,Y)=>r.map((_,X)=>n+=(g=(x,y,z,q=z&2,r=m[y],v=r&&r[x])=>v?(v|=64+(v>{})+!++v)^(r[x]|=v|4<<z)?g(x+--q*~z%2,y-q*z%2,z^2)&g(x,y,z^=v&3?v&1||3:v>>(z^3)&4?1:3)|!(r[x]=v):1:0)(X,Y,0)),n=0)|n

Try it online!

##How?

###Grid encoding

We divide each cell into 4 areas as follows:

areas

The current position is encoded as \$(x,y,z)\$, where \$(x,y)\$ is the position in the matrix and \$z\$ is the ID of the area.

The characters in the original matrix are converted on the fly to 7-bit integers as they are visited:

+---------> a marker to tell that this tile has been converted (always 1)
|      +--> 4 bits to tell whether a given area has been visited
|      |
|      |      +-----> set to 1 if the cell contains an anti-slash
|  ____|____  |  +--> set to 1 of the cell contains a slash
| /         \ |  |
1 z3 z2 z1 z0 AS S

The conversion is done with:

v |= 64 + (v > {}) + !++v

The expression (v > {}) is only true for '\' and !++v is true for either '/' or '\'. If v is already an integer, it is left unchanged.

###Algorithm

Evaluating the area enclosed by slashes is equivalent to counting the number of cells from which we can't escape from the grid, starting from a given area ID. We arbitrary start from area #0, but that would work with any of them as long as it is consistent.

We iterate on all possible starting points and process some kind of flood-filling that takes the area IDs into account.

For each visited cell, we try to move to an adjacent cell (left figure) and to another area within the same cell (right figure).

moves

The recursion stops either when we escape the grid or when we get trapped.

Arnauld
  • 197.7k
  • 20
  • 179
  • 650