SP206 BITMAP - Bitmap 题解

FFTotoro · 2022-10-13 21:47:46 · 题解

这题一眼看上去就是裸的广搜板子，建议评橙或黄。

首先，我们需要定义广搜上下左右四个方向的数组 dx 与 dy，如下：

const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

其次我们开始分析——如果一个点一开始就是 1，那么它的步数就是 0。我们可以利用一个存储 std::tuple 三元组的队列来记录广搜的信息，每个 tuple 存储当前搜到的点的 x 坐标、y 坐标与已经用的步数。

广搜过程如下：

while(!q.empty()){
  int x,y,z; tie(x,y,z)=q.front();
  a[x][y]=z; q.pop();
  for(int i=0;i<4;i++){
    int xx=x+dx[i],yy=y+dy[i]; // 计算可以到达的坐标
    if(xx>=0&&xx<n&&yy>=0&&yy<m&&!b[xx][yy]) // 判断坐标的合法性
      q.emplace(xx,yy,z+1),b[xx][yy]=true; // 步数加一，加入队列继续进行广搜
  }
}

最后将存储的答案输出即可。由于本解法用的是动态数组 std::vector，所以不必担心多测清空的问题。

附上完整代码：

#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define tpi tuple<int,int,int>
// define 可以减少码量，尤其是在数据结构这种大码量题中十分好用
using namespace std;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); // iostream 加速
  int t; cin>>t;
  while(t--){
    int n,m; cin>>n>>m;
    queue<tpi> q;
    vector<vi> a(n,vi(m)); // 答案数组
    vector<vb> b(n,vb(m)); // 标记是否遍历过的数组
    for(int i=0;i<n;i++)
      for(int j=0;j<m;j++){
        char c; cin>>c;
        if(c&1)q.emplace(i,j,0),b[i][j]=true; // 如果是 1 就加入队列
      }
    while(!q.empty()){
      int x,y,z; tie(x,y,z)=q.front();
      a[x][y]=z; q.pop();
      for(int i=0;i<4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=0&&xx<n&&yy>=0&&yy<m&&!b[xx][yy])
          q.emplace(xx,yy,z+1),b[xx][yy]=true;
      }
    } // 广搜部分
    for(int i=0;i<n;i++,cout<<endl)
      for(int j=0;j<m;j++)
        cout<<a[i][j]<<' ';
  }
  return 0;
}