第十二届模拟赛，bfs广度优先搜索

梦里梦外; 2022-11-18 13:58 74阅读 0赞

### 题目描述 小蓝负责花园的灌溉工作。 花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。 ###

小蓝负责花园的灌溉工作。  
花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。)  
小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。  
每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。  
给定花园水管的位置，请问 k k k 分钟后，有多少个方格被灌溉好？  
输入格式  
输入的第一行包含两个整数 n n n, m m m。  
第二行包含一个整数 t t t，表示出水管的数量。  
接下来 t t t 行描述出水管的位置，其中第 i i i 行包含两个数 r , c r, c r,c 表示第 r r r 行第 c c c 列有一个排水管。  
接下来一行包含一个整数 k k k。  
输出格式  
输出一个整数，表示答案。  
样例输入

3 6  
2  
2 2  
3 4  
1

样例输出

样例说明  
用1表示灌溉到，0表示未灌溉到。  
打开水管时：  
　　000000  
　　010000  
　　000100  
1分钟后：  
　　010000  
　　111100  
　　011110  
　　共有9个方格被灌溉好。  
数据规模和约定 　  
对于所有评测用例： 1 ≤ n , m ≤ 100 , 1 ≤ t ≤ 10 , 1 ≤ k ≤ 100 1 \\leq n, m \\leq 100, 1 \\leq t \\leq 10, 1 \\leq k \\leq 100 1≤n,m≤100,1≤t≤10,1≤k≤100。  
将最初水龙头的位置标记，存入队列，再用一个队列存储下一分钟蔓延的位置，每分钟结束，更新队列中的元素，最后输出在规定时间内灌溉的位置有多少个即可。

### 题目描述 小蓝有一张黑白图像，由 n ∗ m n \* m n∗m 个像素组成，其中从上到下共 n n n 行，每行从左到右 m m m 列。每个像素由一个 0 到 255 之间的灰度值表示。 ###

小蓝有一张黑白图像，由 n ∗ m n \* m n∗m 个像素组成，其中从上到下共 n n n 行，每行从左到右 m m m 列。每个像素由一个 0 到 255 之间的灰度值表示。)  
现在，小蓝准备对图像进行模糊操作，操作的方法为：  
对于每个像素，将以它为中心 3 \* 3 区域内的所有像素（可能是 9 个像素或少于 9 个像素）求和后除以这个范围内的像素个数（取下整），得到的值就是模糊后的结果。  
请注意每个像素都要用原图中的灰度值计算求和。  
输入格式  
输入的第一行包含两个整数 n , m n, m n,m。  
第 2 行到第 n + 1 n + 1 n+1 行每行包含 m m m 个整数，表示每个像素的灰度值，相邻整数之间用一个空格分隔。  
输出格式  
输出 n n n 行，每行 m m m 个整数，相邻整数之间用空格分隔，表示模糊后的图像。  
样例输入

3 4  
0 0 0 255  
0 0 255 0  
0 30 255 255

样例输出

0 42 85 127  
5 60 116 170  
7 90 132 191

数据规模和约定  
对于所有评测用例， 1 ≤ n , m ≤ 100 1 \\leq n, m \\leq 100 1≤n,m≤100。

扩展有8个方向（点）扩展，然后以当前这个点为中心向 8 个方向扩展即可，最后按照题意求模糊值。

#include <iostream>
    #include <cstring>
    #include <string>
    #include <queue>
    #include <algorithm>
    using namespace std;
    int vis[110][110];
    int dir[8][2]={
        -1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1} ;//8个点 
    int mp[110][110];
    int ans[110][110];
    bool inbound(int x, int l, int r)
    {
         if(x < l || x > r) return false;//不在范围里
     return true;
    }
    
    int main()
    {
         int n,m; cin>>n>>m;
     for(int i = 1; i <= n; i++) 
     for(int j = 1; j <= m; j++) 
     cin>>mp[i][j]; 
     for(int i = 1; i <= n; i++) 
     {
         for(int j = 1; j <= m; j++)
     
      {
         int t = mp[i][j], cnt = 1; 
      
      for(int k = 0; k <8; k++) 
      {
            int tx = i + dir[k][0];
           int ty = j + dir[k][1]; 
       if(!inbound(tx,1,n) || !inbound(ty,1,m)) 
       continue; 
       t += mp[tx][ty]; 
       cnt++; 
       } 
       ans[i][j] = (int)(t/cnt); 
       } 
       }
       
        for(int i = 1; i <= n; i++) 
    	{
         for(int j = 1; j <= m; j++)
    	 if(j == 1) cout<<ans[i][j]; 
    	 else cout<<" "<<ans[i][j]; cout<<'\n'; } 
    	 return 0;
    }