#54653: 解題思路
uf018127
(Jacob)
每個格子有4個邊，令邊的順序為左上下右，1代表該邊有蛇穿過，0代表沒有，在合法的擺法中，每個格子
都必須是下列幾種狀態之一：
0000: █ # 插座
0011: ┌ # 下右
1001: ─ # 左右
1010: ┐ # 左下
0110: │ # 上下
0101: └ # 上右
1100: ┘ # 左上
我們可以逐格掃描，每格從左格跟上格取左上前綴，則該格可能的選擇有
00: [0011]
01: [0101, 0110]
10: [1001, 1010]
11: [1100]
因為爆搜會TLE所以還要DP，我沒有逐格做DP而是換行的時候做DP，例如現在是第i行剛開始，而i-i行的格子是
┌ ─ ┐ ┌ ─ ┐
狀態可以表達為
(i, 101101) # 1代表該格上邊有蛇穿過，0代表沒有，