Рассмотрим клетку $$$(i, j)$$$ и кратчайшие расстояния от неё до углов решетки. Тогда рассмотрим расстояния до углов $$$(1, 1)$$$ и $$$(1, m)$$$. Эти расстояния равны, соответственно, $$$i+j$$$ и $$$i+(m-j)$$$. Тогда мы можем найти $$$i$$$ как $$$\frac{((i+j) + (i+(m-j)) - m}{2}$$$. И можем найти $$$j$$$ как $$$\frac{((i+j) - (i+(m-j)) + m}{2}$$$.
Таким образом, если мы знаем кратчайшие расстояния до углов решетки, то мы можем однозначно восстановить координаты клетки.
Углам решетки соответствуют вершины степени два данного графа, и если он изоморфен решетке, то таких вершин ровно четыре. Переберем $$$4!$$$ вариантов какая вершина, какому углу соответствует.
Тогда мы для каждой вершины можно найти по формулам выше соответствующую вершину решетки, а затем проверить, что полученная перестановка вершин действительно является изоморфизмом решетки и данного графа.
Таким образом, мы получили решение за $$$\mathcal{O}(4!nm)$$$, что есть $$$\mathcal{O}(nm)$$$.