Превышен лимит времени для расстояния до ближайшей ячейки, имеющей 1 - PullRequest
Новая
       74

Превышен лимит времени для расстояния до ближайшей ячейки, имеющей 1

0 голосов
/ 25 мая 2020

Дана двоичная матрица размером N x M. Задача состоит в том, чтобы найти расстояние до ближайшей единицы в матрице для каждой ячейки. Расстояние рассчитывается как | i1 - i2 | + | j1 - j2 |, где i1, j1 - номер строки и номер столбца текущей ячейки, а i2, j2 - номер строки и номер столбца ближайшей ячейки, имеющей значение 1.

Ввод: первая строка ввода - это целое число T, обозначающее количество тестовых примеров. Затем следуют T-тестовые примеры. Каждый тестовый пример состоит из 2 строк. Первая строка каждого тестового примера содержит два целых числа M и N, обозначающих количество строк и столбцов матрицы. Затем в следующей строке находятся N * M значений матрицы (mat), разделенных пробелом.

Вывод: для каждого тестового примера в новой строке выведите требуемую матрицу расстояний в одной строке, разделенной пробелом. 

 Constraints:
    1 <= T <= 20
    1 <= N, M <= 500

    Example:
        Input:
        2
        2 2 
        1 0 0 1
        1 2
        1 1

    Output:
    0 1 1 0
    0 0

Пояснение: 

Testcase 1:
1 0
0 1
0 at {0, 1} and 0 at {1, 0} are at 1 distance from 1s at {0, 0} and {1, 1} respectively.

Код: 

bool isSafe(int currRow,int currCol,int n,int m){
    return currRow>=0 && currRow<n && currCol>=0 && currCol<m;
}

int bfs(int currX,int currY,vector<int> matrix[],int n,int m) {
    queue<pair<int,int>> q;
    q.push(make_pair(currX,currY));
    static int rows[]={0,-1,0,1};
    static int columns[]={1,0,-1,0};
    int flag=0;
    int dist=0;
    while(flag==0 && !q.empty()) {
        pair<int,int> p=q.front();
        q.pop();
        for(int i=0;i<4;i++) {
            if(isSafe(p.first+rows[i],p.second+columns[i],n,m)) {
                if(matrix[p.first+rows[i]][p.second+columns[i]]) {
                    dist=abs(p.first+rows[i]-currX)+abs(p.second+columns[i]-currY);
                    flag=1;
                    break;
                } else {
                    q.push(make_pair(p.first+rows[i],p.second+columns[i]));
                }
            }
        }
    }

    return dist;

} 

void minDist(vector<int> matrix[],int n,int m) {
    int dist[n][m];
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(matrix[i][j]) {
                dist[i][j]=0;
            } else {
                dist[i][j]=bfs(i,j,matrix,n,m);
            }
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cout<<dist[i][j]<<" ";
        }

    }
}

Agorithm:
1. If matrix[i][j] == 1
      dist[i][j]=0
   else
      dist[i][j]= bfs with source as (i,j)

1 Ответ

1 голос
/ 25 мая 2020

Ваш алгоритм неэффективен, поскольку каждый запуск BFS "только" приводит к обновлению одной ячейки.

Вы должны решать это под другим углом, больше похоже на заливку: выполнять только один обход BFS, начиная со всех узлов, у которых в очереди стоит 1. Затем, пока вы расширяете ячейки, расстояние до которых еще не известно, заполните его.

Вот ваш код, адаптированный к этой идее: 

void minDist(vector<int> matrix[],int n,int m) {
    int dist[n][m];
    vector<pair<int,int>> q; // in this method, we have enough with vector

    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(matrix[i][j]) {
                dist[i][j]=0;
                q.push_back(make_pair(i,j));
            } else {
                dist[i][j]=-1; // undefined distance
            }
        }
    }
    // bfs
    static int rows[]={0,-1,0,1};
    static int columns[]={1,0,-1,0};
    int curdist=1;
    while(!q.empty()) {
        vector<pair<int,int>> q2; // use separate vector for the next extension
        while(!q.empty()) {
            pair<int,int> p=q.back();
            q.pop_back();
            for(int i=0;i<4;i++) {
                if(isSafe(p.first+rows[i],p.second+columns[i],n,m)) {
                    if(dist[p.first+rows[i]][p.second+columns[i]] == -1) {
                        dist[p.first+rows[i]][p.second+columns[i]] = curdist;
                        q2.push_back(make_pair(p.first+rows[i],p.second+columns[i]));
                    }
                }
            }
        }
        q = q2; // Now copy that extension back into the original vector
        curdist++;
    }
    // output
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cout<<dist[i][j]<<" ";
        }
        cout<<"\n";
    }
}
...