Part One
走迷宫的题，遇到障碍物#则转向，按照顺时针的方向，求出最后走出迷宫的足迹范围
....#..... .........# .......... ..#....... .......#.. .......... .#..^..... ........#. #......... ......#...
首先，简单构造出迷宫
with recursive rows as (
SELECT row_number() over () as _row, line
FROM lance_input
), matrix AS (
SELECT _row :: INTEGER, x.idx :: INTEGER as _col, x.pos
FROM rows, regexp_split_to_table(line, '') with ordinality as x(pos, idx)
), cols AS (
SELECT _col, string_agg(pos, '' order by _row) as line
FROM matrix
GROUP BY _col
)
使用递归查询的方式，每次求出当前方向上最远能走到的位置。以^作为起始位置，以走出迷宫作为终止条件
route AS (
SELECT _row, _col, 'N' as direction, 1 as step
FROM matrix
WHERE pos = '^'
UNION ALL
SELECT _row + row_shift as _row,
_col + col_shift as _col,
direction,
step
FROM (
SELECT CASE WHEN direction IN ('N') THEN 1 - position('#' IN reverse(substring(cols.line, 1, route._row - 1)) || '#')
WHEN direction IN ('S') THEN position('#' IN substring(cols.line, route._row + 1) || '#') - 1
ELSE 0
END as row_shift,
CASE WHEN direction IN ('E') THEN position('#' IN substring(rows.line, route._col + 1) || '#') - 1
WHEN direction IN ('W') THEN 1 - position('#' IN reverse(substring(rows.line, 1, route._col - 1)) || '#')
ELSE 0
END as col_shift,
route._row,
route._col,
CASE WHEN direction = 'N' THEN 'E'
WHEN direction = 'E' THEN 'S'
WHEN direction = 'S' THEN 'W'
WHEN direction = 'W' THEN 'N'
END as direction,
step + 1 as step
FROM route
LEFT JOIN rows
ON route._row = rows._row
AND direction IN ('E', 'W')
LEFT JOIN cols
ON route._col = cols._col
AND direction IN ('N', 'S')
WHERE route._row between 2 and 129
AND route._col between 2 and 129
) t
)
最终，走过的足迹，简单去重即可
path AS (
SELECT least(a._row, b._row) as start_row,
least(a._col, b._col) as start_col,
greatest(a._row, b._row) as end_row,
greatest(a._col, b._col) as end_col
FROM route a
JOIN route b
ON a.step + 1 = b.step
)
SELECT DISTINCT x, y
FROM path, generate_series(1, 130) x, generate_series(1, 130) y
WHERE x.id between start_row AND end_row
AND y.id between start_col AND end_col;
Part Two
在迷宫中新放置一个障碍物，从而让其走不出迷宫，求出这些障碍物的位置有几处？
....#..... ....+---+# ....|...|. ..#.|...|. ....|..#|. ....|...|. .#.O^---+. ........#. #......... ......#...
循环路径
让其走不出迷宫，让其绕着一个长方形是最简单的方式，如例子所示。但是，也有场景并不是简单一个长方形，但也是循环，如下图所示。
....#.....
....+---+#
....|...|.
..#.|...|.
..+-+-+#|.
..|.|.|.|.
.#+-^-+-+.
....|.|.#.
#..O+-+...
......#...
障碍物位置候选
分析下出现循环的必要条件，就是障碍物一定要出现在其原有的路径上，从而改变其足迹。所以路径上的所有位置（除去起点，起点不能放置障碍物），都是潜在的候选。
new_pos AS (
SELECT row_number() over () as rn, _row, _col
FROM (
SELECT distinct x as _row, y as _col
FROM path a,
generate_series(1, 130) as x,
generate_series(1, 130) as y,
matrix b
WHERE x between start_row and end_row
AND y between start_col and end_col
AND x = b._row
AND y = b._col
AND b.pos = '.'
) t
)
转向位置判断
之前的判断，是当前方向上遇到的第一个#，然后就转变方向。现在的判断条件，变成了先遇到#，还是先遇到新设的障碍物，判断条件需要更加复杂一些。
row_shift和col_shift是之前的位移量，new_row_shift和new_col_shift是新增障碍物的位移量。
CASE WHEN direction IN ('N') THEN 1 - position('#' IN reverse(substring(cols.line, 1, new_route._row - 1)) || '#')
WHEN direction IN ('S') THEN position('#' IN substring(cols.line, new_route._row + 1) || '#') - 1
ELSE 0
END as row_shift,
CASE WHEN direction IN ('E') THEN position('#' IN substring(rows.line, new_route._col + 1) || '#') - 1
WHEN direction IN ('W') THEN 1 - position('#' IN reverse(substring(rows.line, 1, new_route._col - 1)) || '#')
ELSE 0
END as col_shift,
CASE WHEN direction IN ('N') AND new_pos._col = new_route._col AND new_pos._row < new_route._row THEN new_pos._row - new_route._row + 1
WHEN direction IN ('S') AND new_pos._col = new_route._col AND new_pos._row > new_route._row THEN new_pos._row - new_route._row - 1
END as new_row_shift,
CASE WHEN direction IN ('E') AND new_pos._row = new_route._row AND new_pos._col > new_route._col THEN new_pos._col - new_route._col - 1
WHEN direction IN ('W') AND new_pos._row = new_route._row AND new_pos._col < new_route._col THEN new_pos._col - new_route._col + 1
END as new_col_shift,
循环判断
为了判断循环，需要记录走过的足迹，从而判断是否有重复的位置信息。但是，需要考虑一种特殊情况，就是当前方向上无路可走，原地转向。虽然足迹重复了，但是不能认为就能形成循环，还要看后续的足迹。
比如下图的场景，在起点的正上方摆放了一个障碍物，向下无法继续，只能向右继续。这里虽然在起点的位置上足迹重复了，但是后续并没有重复，而是成功离开了迷宫。因此这里不能算是循环。
....#.....
.........#
..........
..#.......
.......#..
....O.....
.#..^-----
........#.
#.........
......#...
另一个例子，比如下图所示在(2, 6)放置的障碍物，会导致无法向右前进，从而向下继续，从而形成了循环。
....#.....
....|O...#
....|.....
..#.|.....
....|..#..
....|.....
.#..^.....
........#.
#.........
......#...
最终SQL
注意cycle的判断条件，如果是最后一个足迹重复则忽略，继续前进，再判断是否有重复。
new_route AS (
SELECT rn, matrix._row, matrix._col, 'N' as direction, array[matrix._row * 1000 + matrix._col] as path, false as cycle
FROM matrix, new_pos
WHERE pos = '^'
UNION ALL
SELECT rn, _row, _col,
CASE WHEN direction = 'N' THEN 'E'
WHEN direction = 'E' THEN 'S'
WHEN direction = 'S' THEN 'W'
WHEN direction = 'W' THEN 'N'
END as direction,
CASE WHEN (_row * 1000 + _col) = path[#path] THEN path ELSE path || (_row * 1000 + _col) END as path,
(_row * 1000 + _col) = ANY(path[1 : (#path) - 1]) as cycle
FROM (
SELECT _row + CASE WHEN direction = 'N' THEN greatest(row_shift, new_row_shift)
WHEN direction = 'S' THEN least(row_shift, new_row_shift)
ELSE 0
END as _row,
_col + CASE WHEN direction = 'E' THEN least(col_shift, new_col_shift)
WHEN direction = 'W' THEN greatest(col_shift, new_col_shift)
ELSE 0
END as _col,
direction, path, rn
FROM (
SELECT CASE WHEN direction IN ('N') THEN 1 - position('#' IN reverse(substring(cols.line, 1, new_route._row - 1)) || '#')
WHEN direction IN ('S') THEN position('#' IN substring(cols.line, new_route._row + 1) || '#') - 1
ELSE 0
END as row_shift,
CASE WHEN direction IN ('E') THEN position('#' IN substring(rows.line, new_route._col + 1) || '#') - 1
WHEN direction IN ('W') THEN 1 - position('#' IN reverse(substring(rows.line, 1, new_route._col - 1)) || '#')
ELSE 0
END as col_shift,
CASE WHEN direction IN ('N') AND new_pos._col = new_route._col AND new_pos._row < new_route._row THEN new_pos._row - new_route._row + 1
WHEN direction IN ('S') AND new_pos._col = new_route._col AND new_pos._row > new_route._row THEN new_pos._row - new_route._row - 1
END as new_row_shift,
CASE WHEN direction IN ('E') AND new_pos._row = new_route._row AND new_pos._col > new_route._col THEN new_pos._col - new_route._col - 1
WHEN direction IN ('W') AND new_pos._row = new_route._row AND new_pos._col < new_route._col THEN new_pos._col - new_route._col + 1
END as new_col_shift,
new_route._row,
new_route._col,
new_route.direction,
new_route.path,
new_route.rn
FROM new_route
JOIN new_pos
ON new_route.rn = new_pos.rn
LEFT JOIN rows
ON new_route._row = rows._row
AND direction IN ('E', 'W')
LEFT JOIN cols
ON new_route._col = cols._col
AND direction IN ('N', 'S')
WHERE new_route._row between 2 and 129
AND new_route._col between 2 and 129
AND NOT cycle
) t
) s
)
select rn From new_route where cycle;
(1723 rows)
Time: 13226.939 ms (00:13.227)