#JavaScript (ES6), 228 195 192 185 bytes
JavaScript (ES6), 228 195 192 185 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,v&3?z^=v&2|1:z+1&3)|!(r[x]=v):1:0)(X,Y,0)),n=0)|n
##How?
How?
###Grid encoding
Grid encoding
We divide each cell into 4 areas as follows:
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
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).
The recursion stops either when we escape the grid or when we get trapped.