0
votes

Minimiser la distance de Manhattan entre x et y dans une matrice

J'essaie de résoudre une question impliquant la distance et la matrice de Manhattan.

Question: Compte tenu d'une matrice 2D avec laquelle chaque cellule peut contenir un caractère '0' ou 'x' ou 'y'. Trouvez la distance minimale de Manhattan entre X & Y.

distance de Manhattan entre X & Y serait | x (x) - x (y) | + | Y (x) - y (y) |. X & Y représente le numéro de ligne, numéro de colonne resp. de cellule contenant un caractère dans matrice.

Exemple: xxx

est donné et nous devons calculer une distance minimale de Manhattan entre X & Y; Dans ce cas, il est 1 (entre (3,2) et (4,2)).

Une approche de force brute équivaut à O ((m * n) ^ 2) temps, comment peut-il être optimisé pour au moins o (m * n)?

algorithm matrix data-structures

0 commentaires

3 Réponses :

1
votes

C'est un problème de théorie du graphique classique.

Premier avis que la distance de Manhattan n'est que du chemin le plus court sur la grille d'une cellule à l'autre. p>

ajoutez des nœuds marqués avec x à la file d'attente et do BFS jusqu'à ce que vous visitez certains y Le nœud et la distance à ce nœud seront la réponse. p>

Complexité: O (n * m) P>

code d'échantillon (C ++): P>

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;

0 commentaires

0
votes

Sans utilisation de la théorie des graphes

Mettez les coordonnées de tout x_i code> dans ensemble x code> li>
Mettez les coordonnées de tout y_j code> dans ensemble y code> li>
Appliquer la distance sur le produit cartésien de x et y idem Considérez d (x_i, y_j) code> pour tous ij code> li>

 garder le min  li>
 ul>  si  x_s  code> est la taille de  x  code> et  y_s  code> Taille de  y  code>: fonctionne  O (x_sy_s)  code> (en supposant que vous savez où sont  x_i  code> et  y_j  code> ... (O (mn) sinon)  p> 
  p> 


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))))))

0 commentaires

0
votes

Pour chaque cellule de la matrice, la distance minimale de Manhattan n'est que de la distance de la x la plus proche de la gauche et du Y au-dessus de la gauche, ou du X le plus proche de la gauche et du Y au-dessus de la gauche. O (n * m) CODE> Time pour numériser les lignes et les colonnes et O (n) code> la mémoire pour suivre les x et y près dans chaque colonne (par rapport à un O (n * m) code> le pire des cas pour une première recherche de largeur).

def distance(M):
    rows = len(M)
    cols = len(M[0])
    above_x = cols * [-1]
    above_y = cols * [-1]
    res = float('inf')
    for row in range(rows):
        left_x = -1
        left_y = -1
        for col in range(cols):
            # track the nearest x and y to the left and above
            if M[row][col] == 'x':
                above_x[col] = row
                left_x = col
            if M[row][col] == 'y':
                above_y[col] = row
                left_y = col

            # the shortest distance is just the two distances added together
            if left_y > -1 and above_x[col] > -1:
                res = min(res, (col - left_y) + (row - above_x[col]))
            if left_x > -1 and above_y[col] > -1:
                res = min(res, (col - left_x) + (row - above_y[col]))
    return res

0 commentaires