Я решаю проблему с алгоритмом. У меня есть матрица M, которая содержит 0, 1 и 2. Это разреженная матрица. Проблема состоит в том, чтобы использовать самый быстрый способ найти пару 1 и 2 таким образом, чтобы она имела наименьшее расстояние до Манхэттена. Матрица M имеет следующее свойство:
- Для каждой строки в M есть хотя бы один 1.
- Для каждого столбца в M есть как минимум один 2.
Например
M = 0 1 0 2
1 0 0 0
0 2 2 1
2 1 0 1
В этом случае 2 в 3-м ряду, 2-й столбец и 1 в 4-м ряду, 2-й столбец имеет манхэттенское расстояние = 1; 2 в 4-м ряду, 1-й столбец и 1 в 4-м ряду, 2-й столбец имеет манхэттенское расстояние = 1; 2 в 3-м ряду, 3-й столбец и 1 в 3-м ряду, 4-й столбец имеет манхэттенское расстояние = 1;
Мой вопрос: каков самый быстрый способ найти пары, подобные этим 3?
У меня есть все координаты этих 1 и 2. И я могу выполнять параллельные вычисления, то есть, учитывая произвольную 1 запись в матрице M, какой самый быстрый способ найти ближайшие 2 на расстоянии Манхэттена?