【BZOJ 2252】 矩阵距离

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=2252

【算法】

将所有是”1“的点入队，然后广度优先搜索，即可

【代码】

#include<bits/stdc++.h>

using namespace std;

#define MAXN 1010

const int dx[] = {,,-,};

const int dy[] = {-,,,};

int i,j,n,m,tx,ty;

int dist[MAXN][MAXN];

char s[MAXN][MAXN];

char val;

pair<int,int> cur;

queue< pair<int,int> > q;

inline bool ok(int x,int y)

{

        return x >=  && x <= n && y >=  && y <= m;

}

int main()

{

        memset(dist,,sizeof(dist));

        scanf("%d%d",&n,&m);

        for (i = ; i <= n; i++) scanf("%s",s[i]+);

        for (i = ; i <= n; i++)

        {

                for (j = ; j <= m; j++)

                {

                        if (s[i][j] == '')

                        {

                                q.push(make_pair(i,j));

                                dist[i][j] = ;

                        }

                }

        }

        while (!q.empty())

        {

                cur = q.front();

                q.pop();

                for (i = ; i < ; i++)

                {

                        tx = cur.first + dx[i];

                        ty = cur.second + dy[i];

                        if (ok(tx,ty) && dist[tx][ty] == -)

                        {

                                dist[tx][ty] = dist[cur.first][cur.second] + ;

                                q.push(make_pair(tx,ty));

                        }

                }

        }

        for (i = ; i <= n; i++)

        {

                for (j = ; j <= m; j++)

                {

                        printf("%d ",dist[i][j]);

                }

                printf("\n");

        }

        return ;

}