AcWing P173 矩阵距离 题解

Analysis

就是一个裸的广搜，每次从是1的点开始找就好啦~~~

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define maxn 1010

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 queue<pair<int,pair<int,int> > > q;

 int n,m;

 int map[maxn][maxn];

 int ans[maxn][maxn];

 bool book[maxn][maxn];

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

 int main()

 {

     n=read();m=read();

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

     {

         char ch;

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

         {

             cin>>ch;

             map[i][j]=ch-'';

             if(map[i][j]==)

             {

                 ans[i][j]=;

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

             }

         }

     }

     while(!q.empty())

     {

         int ex=q.front().second.first,ey=q.front().second.second,c=q.front().first;

         q.pop();

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

         {

             int xx=ex+dx[i],yy=ey+dy[i];

             if(xx>=&&xx<=n&&yy>=&&yy<=m&&map[xx][yy]!=&&book[xx][yy]==)

             {

                 book[xx][yy]=;

                 ans[xx][yy]=c+;

                 q.push(make_pair(c+,make_pair(xx,yy)));

             }

         }

     }

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

     {

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

         {

             write(ans[i][j]);

             printf(" ");

         }

         printf("\n");

     }

     return ;

 }

请各位大佬斧正（反正我不认识斧正是什么意思）

AcWing P173 矩阵距离 题解的相关教程结束。