LeetCode 1036 - Escape a Large Mazeの別解（？）

https://leetcode.com/contest/weekly-contest-134/submissions/detail/225394673/

問題設定自体は普通の迷路と同じだが，迷路のサイズが10⁶と巨大．

普通にdfsやbfsをしていたのでは到底終わらない．

逆にblocked cellは合計200個以下という制約がある

考えたこと

どういう場合にたどり着けないか．

→広い空間にぱらぱらblockされていれば容易に辿り着ける．

→たどり着けないのは，sourceとtargetが分断されている（局所空間に囲い込まれている）とき．

→blockedは高々200個しかないから，最大の領域をblockできるのは角に斜めに並べたときで，その時中身は19800(=1+2+...+199) cell.

→よってsourceから辿り着ける領域の広さを求め，19800を超えればblockedの魔の手を逃れて広い空間に辿り着けることができる．targetについても同様．

→同じ局所空間内に囲い込まれているケースを除外して，正解が得られる．

当初はblock可能な最大領域を10000と勘違いして提出したのだが，それでもacceptedになってしまったので想定解ではなさそう．

より高速な解法

targetからmanhattan距離で200離れることができれば，必ず逃れられるので，dfsで200超えられるように探索する．多くの場合上記の20000cell探索しなくても解が得られるのでその方が早い．

汎用的な解法

blockedとblockedの間の空白空間はそれが何列あっても1列であっても本質的には変わりない．なので題に登場する座標と前後の一列を保つように座標圧縮してしまえば，通常の迷路の問題と同じアルゴリズムで解ける．

問題となるテストケース

一応反例testcaseとして投稿してみた．

[[0, 199], [1, 198], [2, 197], [3, 196], [4, 195], [5, 194], [6, 193], [7, 192], [8, 191], [9, 190], [10, 189], [11, 188], [12, 187], [13, 186], [14, 185], [15, 184], [16, 183], [17, 182], [18, 181], [19, 180], [20, 179], [21, 178], [22, 177], [23, 176], [24, 175], [25, 174], [26, 173], [27, 172], [28, 171], [29, 170], [30, 169], [31, 168], [32, 167], [33, 166], [34, 165], [35, 164], [36, 163], [37, 162], [38, 161], [39, 160], [40, 159], [41, 158], [42, 157], [43, 156], [44, 155], [45, 154], [46, 153], [47, 152], [48, 151], [49, 150], [50, 149], [51, 148], [52, 147], [53, 146], [54, 145], [55, 144], [56, 143], [57, 142], [58, 141], [59, 140], [60, 139], [61, 138], [62, 137], [63, 136], [64, 135], [65, 134], [66, 133], [67, 132], [68, 131], [69, 130], [70, 129], [71, 128], [72, 127], [73, 126], [74, 125], [75, 124], [76, 123], [77, 122], [78, 121], [79, 120], [80, 119], [81, 118], [82, 117], [83, 116], [84, 115], [85, 114], [86, 113], [87, 112], [88, 111], [89, 110], [90, 109], [91, 108], [92, 107], [93, 106], [94, 105], [95, 104], [96, 103], [97, 102], [98, 101], [99, 100], [100, 99], [101, 98], [102, 97], [103, 96], [104, 95], [105, 94], [106, 93], [107, 92], [108, 91], [109, 90], [110, 89], [111, 88], [112, 87], [113, 86], [114, 85], [115, 84], [116, 83], [117, 82], [118, 81], [119, 80], [120, 79], [121, 78], [122, 77], [123, 76], [124, 75], [125, 74], [126, 73], [127, 72], [128, 71], [129, 70], [130, 69], [131, 68], [132, 67], [133, 66], [134, 65], [135, 64], [136, 63], [137, 62], [138, 61],[139, 60], [140, 59], [141, 58], [142, 57], [143, 56], [144, 55], [145, 54], [146, 53], [147, 52], [148, 51], [149, 50], [150, 49], [151, 48], [152, 47], [153, 46], [154, 45], [155, 44], [156, 43], [157, 42], [158, 41], [159, 40], [160, 39], [161, 38], [162, 37], [163, 36], [164, 35], [165, 34], [166, 33], [167, 32], [168, 31], [169, 30], [170, 29], [171, 28], [172, 27], [173,26], [174, 25], [175, 24], [176, 23], [177, 22], [178, 21], [179, 20], [180, 19], [181, 18], [182, 17], [183, 16], [184, 15], [185, 14], [186, 13], [187, 12], [188, 11], [189, 10], [190, 9], [191, 8], [192, 7], [193, 6], [194, 5], [195, 4], [196, 3], [197, 2], [198, 1], [199, 0]] [0,0] [199,199]