珠海集团网站建设外包,资中网站建设,深圳app制作公司,网络推广方案文案正题
P7151 题目大意
给你一个n*n的方阵#xff0c;有若干机器人的起始点
机器人在每个时间会向一个方向走一步#xff0c;经过D个时间后就会在相邻四个格子复制一个副本#xff0c;副本会和原机器人走相同方向#xff0c;同时也会复制
当任意一个机器人的操作碰到障碍…正题
P7151 题目大意
给你一个n*n的方阵有若干机器人的起始点
机器人在每个时间会向一个方向走一步经过D个时间后就会在相邻四个格子复制一个副本副本会和原机器人走相同方向同时也会复制
当任意一个机器人的操作碰到障碍那么所有机器人都会停止操作
问你最多有多少个位置可以被机器人到达 解题思路
首先从障碍进行一遍bfs找出所有点到最近障碍的距离
然后从所有起始点进行一遍bfs找出到达所有的最短合法路径长度移动过程中不接触到障碍
得到所有点的最短路径后考虑计算副本到达的位置不难发现如果原地不动让副本复制所到达的格子都可以直接向一个方向去到达所以直接扩展给副本即可
code
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 1010
#define mp make_pair
#define fs first
#define sn second
using namespace std;
int n,D,ans,p[N][N],zh[N][N],to[N][N];
char c[N][N];
queuepairint,int d;
priority_queuepairint,pairint,int dd;
const int dx[4]{1,0,-1,0},dy[4]{0,1,0,-1};
void bfs1()
{for(int i1;in;i)for(int j1;jn;j)if(c[i][j]#){d.push(mp(i,j));zh[i][j]0;}else zh[i][j]-1;while(!d.empty()){int xd.front().fs,yd.front().sn;d.pop();for(int i0;i4;i){int txxdx[i],tyydy[i];if(tx0||ntx||ty0||nty)continue;if(zh[tx][ty]-1){zh[tx][ty]zh[x][y]1;d.push(mp(tx,ty));}}}return;
}
void bfs2()
{for(int i1;in;i)for(int j1;jn;j)if(c[i][j]S){d.push(mp(i,j));to[i][j]0;}else to[i][j]-1;while(!d.empty()){int xd.front().fs,yd.front().sn;d.pop();if(to[x][y]/Dzh[x][y])continue;for(int i0;i4;i){int txxdx[i],tyydy[i];if(tx0||ntx||ty0||nty)continue;if(to[tx][ty]-1to[x][y]/Dzh[tx][ty]){//先走再复制所以算当前节点的半径to[tx][ty]to[x][y]1;d.push(mp(tx,ty));}}}return;
}
void bfs3()
{for(int i1;in;i)for(int j1;jn;j)if(to[i][j]0){to[i][j]/D;if(to[i][j]zh[i][j])to[i][j]--;//走到i,j之后不能复制就要特判dd.push(mp(to[i][j],mp(i,j)));}while(!dd.empty()){pairint,pairint,int hdd.top();dd.pop();int vh.fs,xh.sn.fs,yh.sn.sn;if(p[x][y])continue;p[x][y]1;ans;for(int i0;i4;i){int txxdx[i],tyydy[i];if(tx0||ntx||ty0||nty)continue;if(!p[tx][ty]c[tx][ty]!#to[tx][ty]v-1){to[tx][ty]v-1;//向四周扩展dd.push(mp(to[tx][ty],mp(tx,ty)));}}}return;
}
main()
{scanf(%d%d,n,D);for(int i1;in;i)scanf(%s,c[i]1);bfs1();bfs2();bfs3();printf(%d,ans);return 0;
}
