Codeforces Round #533 (Div. 2) D. Kilani and the Game（bfs）-白红宇

Codeforces Round #533 (Div. 2) D. Kilani and the Game（bfs）

阅读量：3898 次

发布时间：2019-05-23

本文共 1126 字，大约阅读时间需要 3 分钟。

【题目】

【题意】

给定一张棋盘（？）的大小和玩家人数，给定玩家的扩散速度和棋盘的初始状态，每个玩家有不少于1个初始点，扩散方式是左上右下四个位置移动，没有玩家可以继续移动时结束，输出每个玩家的扩散范围。

【...】

昨天觉得D题可以挣扎一下，然后搞了一半被喊过去搞C，今天看了下确实是广搜bfs思路没错，所以其实我是有四题的水平但是做题速度太慢了（嘿嘿强行no face一波）。

思路就是按顺序再按速度执行一次可行区域内即左上右下的扩散，一个剪枝就是剪掉已经无法再扩散的玩家部分，防止其因速度过大而再进行不必要的搜索而超时。

需要注意两点：

1.初始位置可以不止一个。

2.最后情况有可能出现大家都走不了了但是还存在可扩散区域 '.' 的情况。

“题意虐我千百遍，我待题意如初恋。” && “好的读题等于成功了一半。” == true

【代码】

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define mem(a,b) memset(a,b,sizeof(a))#define Pi acos(-1)#define eps 1e-8using namespace std;typedef long long int ll;const int maxn=1e5+5;const int inf=0x3f3f3f3f;const int mod=1e9+7;const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};char mp[1005][1005];int ans[10]={0};int s[10];int sum=0,n,m,p,c,cou;queue 
                
                  f[20]; //奇数位存x，偶数位存ybool check(int x,int y){ return x&&y&&x<=n&&y<=m&&mp[x][y]=='.';}void bfs(int t){ for(int i=0;i
                 
                  ='1'&&mp[i][j]<='9') //存入初始点的坐标 f[2*(mp[i][j]-='0')-1].push(i),f[2*mp[i][j]].push(j),sum++,ans[mp[i][j]]++; else if(mp[i][j]=='#') sum++; } c=n*m; while(sum

转载地址：http://kfben.baihongyu.com/

你可能感兴趣的文章