Part One
走迷宫，从左上入口处能够尽早地移动到右下出口处，途中需要避免相遇匀速前进的
#.######
#>>.<^<#
#.<..<<#
#>v.><>#
#<^v^^>#
######.#
是否相遇？
由于蜥蜴的移动是匀速的，因此根据初始位置，以及当前的步数，就可以推断出某一处位置是否安全。因此，函数的入参为初始位置、当前步数、判断位置，出参就是是否安全。
CREATE OR REPLACE FUNCTION is_safe(blizzards INTEGER[], step INTEGER, target INTEGER, loop INTEGER)
RETURNS BOOLEAN AS $$
BEGIN
FOR i IN 1..(#blizzards) LOOP
IF ((blizzards[i] + step - 2) % loop + 2) = target THEN
return false;
END IF;
END LOOP;
RETURN true;
END;
$$ LANGUAGE plpgsql;
蜥蜴的移动是循环的，因此也要给出循环的步数，即移动多少步后回到原点。
WITH recursive origin AS (
SELECT rn as _row, x.idx as _col, x.word as pos
FROM (
SELECT row_number() over() as rn, line
FROM lance_input
) t, regexp_split_to_table(line, '') with ordinality as x(word, idx)
), move_range AS (
SELECT (select count(*) - 2 from origin where _col = 1) :: INTEGER as row_cnt,
(select count(*) - 2 from origin where _row = 1) :: INTEGER as col_cnt
)
东西南北四个方向上均有蜥蜴，因此求出其四个方向上的初始条件
east_blizzard as (
SELECT _row, array_agg(_col) :: INTEGER[] as pos_array
FROM origin
WHERE pos = '>'
GROUP BY _row
), west_blizzard as (
SELECT _row, array_agg(_col) :: INTEGER[] as pos_array
FROM origin
WHERE pos = '<'
GROUP BY _row
), south_blizzard as (
SELECT _col, array_agg(_row) :: INTEGER[] as pos_array
FROM origin
WHERE pos = 'v'
GROUP BY _col
), north_blizzard as (
SELECT _col, array_agg(_row) :: INTEGER[] as pos_array
FROM origin
WHERE pos = '^'
GROUP BY _col
)
迷宫行走
每次行走，除了东西南北四个移动方向外，还可以原地不动，因此每一轮都有5个候选移动目的地
SELECT CASE WHEN move_direction = 'N' THEN _row - 1
WHEN move_direction = 'S' THEN _row + 1
ELSE _row
END as _row,
CASE WHEN move_direction = 'W' THEN _col - 1
WHEN move_direction = 'E' THEN _col + 1
ELSE _col
END as _col,
route || move_direction as route,
step + 1 as step
FROM inner_table, (SELECT regexp_split_to_table('NSWEO', '') as move_direction) s
候选目的地是否合法，判断依据就是
- 只能移动到有效位置，包括起点、终点以及中间的非边界位置
- 东西南北四个方向上的蜥蜴不能相遇
最终，候选位置要进行去重。因此只统计最短路径，中间具体的路径怎么走其实并不重要。终止条件，就是终于走到了最后一行。
完整行走语句
walkthrough AS (
SELECT 1 as _row, 2 as _col, '' as route, 0 as step
UNION ALL
SELECT _row, _col, route, step
FROM (
WITH inner_table AS (
SELECT * FROM walkthrough
), possible_moves AS (
SELECT t._row, t._col, route, step,
row_number() over (PARTITION BY t._row, t._col) as rn
FROM (
SELECT _row, _col, route, step
FROM (
SELECT CASE WHEN move_direction = 'N' THEN _row - 1
WHEN move_direction = 'S' THEN _row + 1
ELSE _row
END as _row,
CASE WHEN move_direction = 'W' THEN _col - 1
WHEN move_direction = 'E' THEN _col + 1
ELSE _col
END as _col,
route || move_direction as route,
step + 1 as step
FROM inner_table, (SELECT regexp_split_to_table('NSWEO', '') as move_direction) s
WHERE NOT EXISTS(SELECT * FROM inner_table WHERE _row = (select row_cnt + 2 from move_range))
) t, move_range r
WHERE ((_row between 2 AND (r.row_cnt + 1) AND _col between 2 AND (r.col_cnt + 1))
OR (_row = r.row_cnt + 2 AND _col = r.col_cnt + 1))
OR (_row = 1 AND _col = 2)
) t
JOIN move_range m
ON 1 = 1
LEFT JOIN east_blizzard e
ON t._row = e._row
LEFT JOIN west_blizzard w
ON t._row = w._row
LEFT JOIN north_blizzard n
ON t._col = n._col
LEFT JOIN south_blizzard s
ON t._col = s._col
WHERE (e._row IS NULL OR is_safe(e.pos_array, step, t._col, col_cnt))
AND (w._row IS NULL OR is_safe(w.pos_array, col_cnt - (step % col_cnt), t._col, col_cnt))
AND (s._col IS NULL OR is_safe(s.pos_array, step, t._row, row_cnt))
AND (n._col IS NULL OR is_safe(n.pos_array, row_cnt - (step % row_cnt), t._row, row_cnt))
)
SELECT x._row, x._col, x.route, x.step
FROM possible_moves x
WHERE rn = 1
) t
)
Part Two
忘记拿东西……，需要走终点走回到起点，再回到终点。
初始条件修改即可
SELECT 1 as _row, 2 as _col, 0 as step
修改为
SELECT destination_row, destination_col, xx as step