Минимизируйте манхэттенское расстояние между матрицами x и y

Question

Я пытаюсь решить вопрос, связанный с расстоянием и матрицей Манхэттена.

Вопрос: Учитывая двумерную матрицу, в которой каждая ячейка может содержать либо символ «0», либо «x», либо «y». Найдите минимальное расстояние Манхэттена между x & y.

Манхэттенское расстояние между x & y будет | X (x) - X (y) |+ | Y (x) - Y (y) |. X & Y представляет номер строки, номер столбца соответственноячейки, содержащей символ в матрице.

Пример:

[ x, 0, 0, 0 ]
[ 0, y, 0, y ]
[ x, x, 0, 0 ]
[ 0, y, 0, 0 ]

дано, и мы должны вычислить минимальное Манхэттенское расстояние между x & y;в этом случае это 1 (между (3,2) и (4,2)).

Подход грубой силы может составить O ((m * n) ^ 2) времени, как это может бытьоптимизирован, по крайней мере, O (m * n)?

Answer 1

Это классическая проблема теории графов.

Сначала обратите внимание, что Манхэттенское расстояние - это просто кратчайший путь в сетке от одной ячейки к другой.

Затем добавьте узлы, отмеченные xв очередь и делайте BFS , пока не посетите какой-нибудь узел y, и расстояние до этого узла будет ответом.

Сложность: O (n * m)

Пример кода (C ++):

int n = 4;
const int inf = 1234567890;
vector<string>M = {"x000","0y0y","xx00","0y00"};
vector<vector<int>>D(n, vector<int>(n,inf));
queue<array<int,2>>Q;

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
    if(M[i][j]=='x')
{
    Q.push({i,j});
    D[i][j]=0;
}

int res = inf;

while(!Q.empty())
{
    int row = Q.front()[0];
    int col = Q.front()[1];
    if(M[row][col]=='y')
    {
        res=D[row][col];
        break;
    }
    Q.pop();

    int dr[] = {-1,1,0,0};
    int dc[] = {0,0,-1,1};

    for(int k=0; k<4; k++)
    {
        int r = row + dr[k];
        int c = col + dc[k];
        if(min(r,c) >=0 && max(r,c) < n && D[r][c]==inf)
        {
            D[r][c]=D[row][col]+1;
            Q.push({r,c});
        }
    }
}

cout<<res;

Answer 2

без использования теории графов

• положить координаты любого x_i в наборе x
• положить координаты любого y_j в наборе y
• применить расстояние к декартовому произведению x и y. То же самое: d(x_i, y_j) для всех ij
• оставьте мин

, если x_s равно X и y_s размер Y: работает в O(x_sy_s) (при условии, что вы заранее знаете, где находятся x_i и y_j ... (O (mn) в противном случае)

let {x,y} = `x000,0y0y,xx00,0y00`.replace(/,/g,'').split('').reduce((acc,v,id)=>{
    let y = id%4;
    let x = (id-y)/4
    if(v=='x'||v=='y'){
        acc[v].push([x,y]);
    }
    return acc;
},{x:[],y:[]})
let d = (a,b)=>Math.abs(a[1]-b[1])+Math.abs(a[0]-b[0]);
console.log('dist:', Math.min(...x.map(v=>Math.min(...y.map(w=>d(v,w))))))