CodeForces - 1335F Robots on a Grid(拓扑找环+反向dfs/倍增)

题目链接：点击查看

题目大意：给出一个 n * m 的矩阵，矩阵的每一个格子都有一个颜色，颜色非黑即白，除此之外每个格子还有一个指令，分别为：

' U '：向上一个单位

' D '：向下一个单位

' R '：向右一个单位

' L '：向左一个单位

每个格子都可以放置机器人，对于每个机器人而言，每一秒都会遵循格子上的指令行走，换句话说，机器人会永不停止的行走，现在问，如何放置机器人，可以使得矩阵中机器人的数量最多，且互相永远不会冲突，即任意时刻每个格子里至多有只能一个机器人，在满足矩阵中机器人数量最多的前提下，如何摆放可以使得在黑色格子上的机器人最多，分别输出这两个答案

题目分析：这个题目两个思路，一种思路比较好想，但是细节较多，码量较大，另一种思路需要一定的思维，实现简单，码量小

先从第一种思路说起，因为机器人会永不停止的行走，就说明矩阵中一定存在着首尾相接的环，显然所有环的长度之和就是ans1了，也可以知道了ans1与颜色无关，对于ans2我们需要多考虑一点东西：

 在上面这个情况中，点1和点2已经组成了一个首尾相接的环路，所以ans1显然为 2 ，就不多赘述了，但是加上颜色的限制，如果点1和点2同为白色，但是点3为黑色，那么初始时最优的摆放策略肯定是摆在点3和点2，因为这样既能满足ans1=2，且ans2=1，这种情况该如何考虑呢？对于环上的任意一个节点开始，沿着反向边进行遍历，跑出 dis 距离数组就行了，显然如果在这样一个整体中，如果最终不想冲突的话，dis[ i ] % len 的位置上至多只能有一个机器人，此处的 len 为首位相接的环路长度

想清楚上面 dis[ i ] % len 这个地方后，实现就好了，重新捋一下这个题的过程，首先整个矩阵可以视为一个 n * m 个结点和 n * m 条边组成的有向图，既然是有向图，就可以拓扑找环，根据拓扑排序的性质将整个图处理到只剩下首尾相接的环路，此后对于每个环路而言，找到上面的任意一个结点开始，反向 dfs 跑出 dis 数组，然后判断就好了

细节较多，代码如下：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;const int b[4][2]={0,1,0,-1,1,0,-1,0};int mp[150];int n,m,len,du[N],deep[N];//du:入度 deep:在环上的相对位置 len:环的长度 string maze[N],color[N];vector<int>node[N],out[N];//正向边与反向边vector<int>black[N];//black[i]:以点 i 为根节点的环中所牵连的黑点 bool vis[N],flag[N];//vis:是否在环上 flag:找黑点上机器人时用 inline void addedge(int u,int v) {node[u].push_back(v);out[v].push_back(u);du[v]++; }inline int get_id(int x,int y) {return x*m+y; }void topo()//拓扑找环 {queue<int>q;for(int i=0;i<n*m;i++)if(!du[i])q.push(i);while(q.size()){int u=q.front();q.pop();for(auto v:node[u])if(--du[v]==0)q.push(v);} }void dfs(int u,int rt,int dep) {vis[u]=true;deep[u]=dep;if(color[u/m][u%m]=='0')black[rt].push_back(u);for(auto v:out[u]){if(vis[v]){len=deep[u];continue;}dfs(v,rt,dep+1);} }inline void init() {for(int i=0;i<n*m;i++){node[i].clear();out[i].clear();black[i].clear();vis[i]=flag[i]=du[i]=0;} }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);mp['R']=0,mp['L']=1,mp['D']=2,mp['U']=3;int w;cin>>w;while(w--){scanf("%d%d",&n,&m);init();for(int i=0;i<n;i++)cin>>color[i];for(int i=0;i<n;i++)cin>>maze[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++){int k=mp[maze[i][j]];addedge(get_id(i,j),get_id(i+b[k][0],j+b[k][1]));}topo();int ans1=0,ans2=0;for(int i=0;i<n*m;i++)if(du[i]&&!vis[i])//在环上且没遍历过，遍历一遍这个环{dfs(i,i,1);ans1+=len;for(auto v:black[i])if(!flag[deep[v]%len]){flag[deep[v]%len]=true;ans2++;}for(auto v:black[i])flag[deep[v]%len]=false;}printf("%d %d\n",ans1,ans2);}return 0; }

下面说一下第二种思路，假如两个机器人会冲突的话，也就是说在某个时刻，某个格子中同时出现了两个机器人，那么在接下来的移动过程中，显然这两个机器人的路径将保持一致，我们可以先假设 n * m 个格子中初始时都有一个机器人，先让这些机器人运动 n * m 秒，甚至更多，因为 n * m 的一个矩阵，最大可以形成的一个首尾相接的环路长度就是 n * m ，所以先让所有机器人都运动 n * m 秒后，该重合的机器人都已经重合了，并且不难统计每个位置中有多少个来自黑格的机器人，此时矩阵中仍然有机器人的地方，就说明这个位置是首尾相接的环，那么ans1++，如果这个地方至少有一个来自黑格的机器人，那就说明来到这个位置的机器人初始时可以摆在黑格上，即ans2++

实现的话肯定不是暴力模拟 n * m 秒，可以利用倍增，首先将 n * m 个格子按照 0 ~ n * m - 1 编号，那么 dp[ i ][ j ] 就代表编号为 i 的点走 2^j 步可以到达的地方，这里类比于树上倍增就好，剩下的实现起来就比较简单了

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;const int b[4][2]={0,1,0,-1,1,0,-1,0};int mp[150];string maze[N],color[N];int dp[N][20],n,m,num[N][2];//num[i][0]:black num[i][1]:whiteinline int get_id(int x,int y) {return x*m+y; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);mp['R']=0,mp['L']=1,mp['D']=2,mp['U']=3;int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=0;i<n*m;i++)num[i][0]=num[i][1]=0;int limit=log2(n*m)+1;for(int i=0;i<n;i++)cin>>color[i];for(int i=0;i<n;i++)cin>>maze[i];for(int i=0;i<n;i++)for(int j=0;j<m;j++){int k=mp[maze[i][j]];dp[get_id(i,j)][0]=get_id(i+b[k][0],j+b[k][1]);}for(int j=1;j<=limit;j++)for(int i=0;i<n*m;i++)dp[i][j]=dp[dp[i][j-1]][j-1];for(int i=0;i<n;i++)for(int j=0;j<m;j++)num[dp[get_id(i,j)][limit]][color[i][j]-'0']++;int ans1=0,ans2=0;for(int i=0;i<n*m;i++){ans1+=!!(num[i][1]+num[i][0]);//大佬代码学到的，判断一个数是否非零，tqlans2+=!!num[i][0];}printf("%d %d\n",ans1,ans2);}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1335F Robots on a Grid(拓扑找环+反向dfs/倍增)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。