ABC197 F Construct a Palindrome
頂点数$ N^2の無向グラフに帰着する. 辺はもとのグラフ上の頂点$ a, b, c, dについて, $ aと$ c, $ bと$ dの間に辺があり, かつそれらの辺に書かれている文字が同じ場合に$ (a, b)から$ (c, d)へ張ればよい. 陽にグラフを持っても間に合う. このように辺を張るとそれをたどっていくことで回文にできるので, あとはその最短の長さを求めたい. これはBFSを用いて求めることができる. 計算量は$ O(max(N^2, M^2))となる.