题目描述
bfs进入队列时，值一定是最小的，只会被更新一次，入队之后不会被更新
超时了，以为入队之后还需要更新，但实际上入队之后那个值已经必是最小的了，因为bfs的性质就是这样，入队的每个点必已经是最小距离
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int N=1010;
typedef pair<int,int> pii;
int n,m;
int dist[N][N];
char s[N][N];
int st[N][N];
int main()
{
cin>>n>>m;
queue<pii> q;
queue<pii> o;
memset(dist,0x3f,sizeof dist);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>s[i][j];
if(s[i][j]=='1') dist[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='1') q.push({i,j});
}
}
int dx[]={0,-1,1,0};
int dy[]={1,0,0,-1};
while(q.size())
{
auto qt=q.front();
q.pop();
o.push(qt);
memset(st,0,sizeof st);
while(o.size())
{
auto t=o.front();
o.pop();
for(int i=0;i<4;i++)
{
int a=t.first+dx[i];
int b=t.second+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&st[a][b]==0 && s[a][b]=='0')
{
o.push({a,b});
st[a][b]=1;
dist[a][b]=min(dist[a][b],dist[t.first][t.second]+1);
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
AC代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int N=1010;
typedef pair<int,int> pii;
int n,m;
int dist[N][N];
char s[N][N];
int st[N][N];
int main()
{
cin>>n>>m;
queue<pii> q;
queue<pii> o;
memset(dist,-1,sizeof dist);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>s[i][j];
if(s[i][j]=='1') dist[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(s[i][j]=='1') q.push({i,j});
}
}
int dx[]={0,-1,1,0};
int dy[]={1,0,0,-1};
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int a=t.first+dx[i];
int b=t.second+dy[i];
if(a>=1&&a<=n&&b>=1&&b<=m&&dist[a][b]==-1 && s[a][b]=='0')
{
q.push({a,b});
//st[a][b]=1;
dist[a][b]=dist[t.first][t.second]+1;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
二刷，要了解bfs的性质
每个点只更新自己周围的一圈，这样保证更新到的距离一定是最小的(如果一个点先被更新，那这个距离一定是最小的，之后再遍历到他，距离不可能比第一次遍历到他的时候小)，且一个点只会被更新一次
因为队列是按距离从小到大排序的（一定是这样，因为先进去的点是距离为0的，之后再进去的是1的…以此类推
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1010;
typedef pair<int,int> pii;
queue<pii> q;
char w[N][N];
int st[N][N];
int n,m;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int dist[N][N];
int main()
{
cin>>n>>m;
memset(dist,-1,sizeof dist);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>w[i][j];
if(w[i][j]=='1')
{
q.push({i,j});
dist[i][j]=0;
}
}
}
while(q.size())
{
auto t=q.front();
q.pop();
int x=t.first;
int y=t.second;
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
if(a<=n&&a>=1&&b<=m&&b>=1&&dist[a][b]==-1&&w[a][b]=='0')
{
q.push({a,b});
dist[a][b]=dist[x][y]+1;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
三刷 ok
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=10010;
int n,m;
char g[N][N];
typedef pair<int,int> pii;
queue<pii> q;
int dist[N][N];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
if(g[i][j]=='1') q.push({i,j});
}
}
while(q.size())
{
auto t=q.front();
q.pop();
int x=t.first;
int y=t.second;
for(int i=0;i<4;i++)
{
int a=x+dx[i];
int b=y+dy[i];
if(a>=1 && a<=n && b>=1 &&b<=m &&dist[a][b]==0 &&g[a][b]=='0')
{
dist[a][b]=dist[x][y]+1;
q.push({a,b});
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
2023/12/1
要注意用bfs的性质：每次第一次遍历到，就是最短路！
具体步骤如下：
1. 将所有为1的点入队，并且初始化距离为0
2. 遍历周围为0的点
3. 所有的1， 依次开始去找相邻的0，然后更新距离
4. 这样保证了每个0第一次被更新距离时一定是最短的，所以直接把st设置为1，避免第二次被更新
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N=1010;
int dx[]={1, 0, -1, 0};
int dy[]={0, 1, 0, -1};
int n, m;
char g[N][N];
int st[N][N];
int dist[N][N];
typedef pair<int,int> pii;
queue<pii> q;
int main()
{
cin>>n>>m;
memset(dist, 0x3f, sizeof(dist));
int sx, sy;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>g[i][j];
if(g[i][j] == '1')
{
dist[i][j] = 0;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(g[i][j]=='1')
{
q.push({i,j});
st[i][j] = 1;
}
}
}
while(q.size())
{
auto t = q.front();
q.pop();
int x=t.first;
int y=t.second;
for(int k=0;k<4;k++)
{
int a=x+dx[k];
int b=y+dy[k];
// 如果范围合法，且g[i][j]为0
if(a>=1 && b>=1 && a<=n && b<=m && g[a][b]=='0' && st[a][b] == 0)
{
dist[a][b] = min(dist[a][b], dist[x][y] + 1);
q.push({a,b});
st[a][b] = 1;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
