ドアが存在する行を小さい順に \(A'_1, \cdots, A'_{|A'|}\) とし，\(A'_i\) 行目でドアがある列番号を小さい順に \(B'_{i,\ 1} \cdots, B'_{i,\ |B'_i|}\) とおきます．

各マスを頂点とし，マス間の移動を辺を張る行為として解釈すると，この問題はドアをもつ \(N\) マスおよびマス \((1,1)\) をすべて通るオイラー路の総距離の最小値を求める問題として言い換えられます．

\(1\) 行目から \(A'_i\) 行目までの状態を表す DP テーブル \(dp_i[s][t][c]\) を，以下の添字で定義します．

• \(s\) は，マス \((A'_i,\ 1)\) の次数が \(0\)，正の奇数，正の偶数のどれにあたるかを表す．
• \(t\) は，マス \((A'_i,\ W)\) の次数が \(0\)，正の奇数，正の偶数のどれにあたるかを表す．
• \(c\) は，マス \((A'_1,\ 1)\) とマス \((A'_1,\ W)\) がともに正の次数をもち，かつ非連結であるかどうかを表す．

このとき，\(dp_{i-1}\) から \(dp_{i}\) への遷移は，以下の総当たりによって書けます．

• マス \((A'_{i-1},\ 1), (A'_{i},\ 1)\) 間の辺の本数が \(0,1,2\) のいずれか
• マス \((A'_{i-1},\ W), (A'_{i},\ W)\) 間の辺の本数が \(0,1,2\) のいずれか
• \(A'_{i}\) 行目のなかでの辺の張り方が以下のどれにあたるか(列番号 \(j\) でマス \((A'_i,\ j)\) を表す)
  • マス \(1\) からマス \(W\) まで，\(1\) 本ずつ辺を張る
  • マス \(1\) からマス \(B'_{|B'_i|}\) まで，\(2\) 本ずつ辺を張る
  • マス \(B'_{1}\) からマス \(W\) まで，\(2\) 本ずつ辺を張る
  • マス \(1\) からマス \(B'_{j+0}\) まで，およびマス \(B'_{j+1}\) からマス \(W\) まで，\(2\) 本ずつ辺を張る

各頂点での次数の偶奇・符号，および連結性に矛盾が生じないように遷移を書くことで，\(\displaystyle \min_{(s,t) \neq (0,0)} dp_{|A'|}[s][t][\mathrm{connected}]\) が答えになります．

実装例 (C++, 112 ms)

原案：sheyasutaka