Пусть клетки таблицы будут вершинами графа. Ребрами соединим клетки, имеющие общую сторону. Нетрудно убедиться, что расстояние между клетками таблицы равно расстоянию между соответсвующими им вершинами в графе. Обойдем граф в ширину, в начале добавив в очередь все вершины, соответствующие клеткам, содержащим 1. Полученные расстояния и будут ответом на поставленную задачу.
Как и в предыдущей задаче, граф не нужно хранить в памяти компьютера.