Маленькое предположение - а не получится разложить или развернуть квадрат в дерево с корнем в I, а потом просто различные обходы делать??? ИМХО если получится, то тогда можно опять же стандартными контейнерами решить, что в разы быстрее тривиального перебора...
Не утверждаю что так получится, но вдруг
