Заметим, что, зная текущую позицию одного человека и начальные позиции обоих, можно однозначно восстановить текущую позицию второго. Пусть начальные позиции равны $$$(a_0,b_0) \text{ и } (c_0,d_0)$$$, а текущая позиция первого — $$$(a_1,b_1)$$$. Тогда текущая позиция второго равна $$$$$$ \bigl((c_0 + a_0 - a_1)\bmod n, (d_0 + b_0 - b_1)\bmod m\bigr). $$$$$$ Отсюда следует, что существует не более $$$n\cdot m$$$ различных пар состояний $$$((a,b),(c,d))$$$, в которых оба человека могут одновременно находиться. Поэтому достаточно построить граф этих состояний и запустить по нему BFS, проверяя достижимость любого состояния вида $$$((a,b),(a,b))$$$ (то есть совпадения позиций). Поскольку из каждой вершины графа исходит не более 4 переходов, время работы и требуемая память составляют $$$\mathcal{O}(n\cdot m)$$$.