173 矩阵距离

算法1

(暴力枚举) $O(n^2)$

暴力枚举的思路即依次遍历整个数组的每一位，然后对每一个位置进行bfs操作，返回其距离最近的1的距离，因为时间复杂度过高，会TLE

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 2000;
int n,m;

//b数组用于存放所有的点的内容，d数组存放距离，tmp数组存放当前这个点bfs过程中的中间距离，v数组表示是否被遍历过
int b[N][N],d[N][N],tmp[N][N],v[N][N];
char nn[N][N];

int bfs(int x,int y)
{
    memset(tmp, 0, sizeof tmp);
    memset(v, -1, sizeof v);
    queue<pair<int,int>> q;
    q.push({x,y});

    if(b[x][y] == 1)    return 0;

    while(q.size())
    {
        pair<int,int> t = q.front();
        q.pop();

        int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
        for(int i = 0; i < 4; i ++ )
        {
            int dis = tmp[t.first][t.second];
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x >= 0 && x < n && y >=0 && y < m && v[x][y] == -1)
            {
                if(b[x][y] == 1)
                {
                    //cout<<x<<" "<<y<<" "<<b[x][y]<<endl;
                    return dis + 1;
                }    
                else
                {
                    tmp[x][y] = dis + 1;
                    q.push({x,y});
                    v[x][y] = 1;
                }
            }
        }
    }
}

int main()
{
    memset(d, 0, sizeof d);
    cin>>n>>m;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            cin>>nn[i][j];
            b[i][j] = nn[i][j] - '0';
        }
        getchar();
    }

    //依次搜索每一个点
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            d[i][j] = bfs(i,j);

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
            printf("%d ",d[i][j]);
        puts("");
    }


    return 0;
}

算法2 倒搜

如果把每个节点都bfs一遍，无疑之前节点的信息也没法被记忆，而且即使记忆了也不具有最优性的结论，相反，如果我们从值为1的节点开始倒着搜，那么第一遍搜到的就绝对是最近的点，以此类推，就可以把所有最近的点依次搜出来，而且此方法具有记忆性，可以利用上一个结点的距离求出当前节点的最短距离

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 2000;
int n,m;
int b[N][N],d[N][N];
char nn[N][N];

void bfs()
{
    queue<pair<int,int>> q;

    //先把所有值为1的点压入队列之中
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            if(b[i][j] == 1)
            {
                q.push({i,j});
            }

    //bfs的顺序为，首先先搜1周围的点，1搜完之后再去搜1衍生出来的点，注意这是广搜，不是深搜，所以不会一次性就把所有点的距离全部填满，而是辐射性的慢慢填满
    while(q.size())
    {
        pair<int,int> t = q.front();
        q.pop();

        int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
        for(int i = 0; i < 4; i ++ )
        {
            int dis = d[t.first][t.second];
            int x = t.first + dx[i], y = t.second + dy[i];
            //如果当前节点合法，且其没有被辐射到过，说明当前距离就是最小距离了
            if(x >= 0 && x < n && y >=0 && y < m && d[x][y] == -1)
            {
                d[x][y] = dis + 1;
                q.push({x,y});
            }
        }
    }
}

int main()
{
    memset(d, -1, sizeof d);
    cin>>n>>m;

    //数据处理，一开始载坑里了，直接当作整型数组在读入
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            cin>>nn[i][j];
            b[i][j] = nn[i][j] - '0';
            //如果是1，初始化距离数组的值为0
            if(b[i][j] == 1)
                d[i][j] = 0;
        }
        //吃掉换行
        getchar();
    }


    bfs();

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
            printf("%d ",d[i][j]);
        puts("");
    }


    return 0;
}