There is a rectangular grid of size n×m. Each cell of the grid is colored black (‘0’) or white (‘1’). The color of the cell (i,j) is ci,j. You are also given a map of directions: for each cell, there is a direction si,j which is one of the four characters ‘U’, ‘R’, ‘D’ and ‘L’.

If si,j is ‘U’ then there is a transition from the cell (i,j) to the cell (i?1,j);
if si,j is ‘R’ then there is a transition from the cell (i,j) to the cell (i,j+1);
if si,j is ‘D’ then there is a transition from the cell (i,j) to the cell (i+1,j);
if si,j is ‘L’ then there is a transition from the cell (i,j) to the cell (i,j?1).
It is guaranteed that the top row doesn’t contain characters ‘U’, the bottom row doesn’t contain characters ‘D’, the leftmost column doesn’t contain characters ‘L’ and the rightmost column doesn’t contain characters ‘R’.

You want to place some robots in this field (at most one robot in a cell). The following conditions should be satisfied.

Firstly, each robot should move every time (i.e. it cannot skip the move). During one move each robot goes to the adjacent cell depending on the current direction.
Secondly, you have to place robots in such a way that there is no move before which two different robots occupy the same cell (it also means that you cannot place two robots in the same cell). I.e. if the grid is “RL” (one row, two columns, colors does not matter there) then you can place two robots in cells (1,1) and (1,2), but if the grid is “RLL” then you cannot place robots in cells (1,1) and (1,3) because during the first second both robots will occupy the cell (1,2).
The robots make an infinite number of moves.

Your task is to place the maximum number of robots to satisfy all the conditions described above and among all such ways, you have to choose one where the number of black cells occupied by robots before all movements is the maximum possible. Note that you can place robots only before all movements.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤5?104) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and m (1<nm≤106) — the number of rows and the number of columns correspondingly.

The next n lines contain m characters each, where the j-th character of the i-th line is ci,j (ci,j is either ‘0’ if the cell (i,j) is black or ‘1’ if the cell (i,j) is white).

The next n lines also contain m characters each, where the j-th character of the i-th line is si,j (si,j is ‘U’, ‘R’, ‘D’ or ‘L’ and describes the direction of the cell (i,j)).

It is guaranteed that the sum of the sizes of fields does not exceed 106 (∑nm≤106).

Output
For each test case, print two integers — the maximum number of robots you can place to satisfy all the conditions described in the problem statement and the maximum number of black cells occupied by robots before all movements if the number of robots placed is maximized. Note that you can place robots only before all movements.

Example
Input
3
1 2
01
RL
3 3
001
101
110
RLL
DLD
ULL
3 3
000
000
000
RRD
RLD
ULL
Output
2 1
4 3
2 2
題意：有一個(gè)包含n*m個(gè)格子的圖形，每一個(gè)格子被染成黑色（0）或者白色（1）。每一個(gè)格子都有指定的指向，或上或下或左或右。每一個(gè)格子最多只能放置一個(gè)機(jī)器人，所有的機(jī)器人一起移動，不允許多個(gè)機(jī)器人處在同一個(gè)格子，時(shí)間是無限長的。問最多可以放置多少個(gè)機(jī)器人。在這一前提下，最多有多少機(jī)器人一開始可以放置在黑色的格子里。
思路：因?yàn)闀r(shí)間是無限長的，所以若想滿足條件，只能無限循環(huán)，這就要求我們?nèi)フ疫@個(gè)有向圖中的所有的環(huán)，求環(huán)之前需要拓?fù)渑判蛞幌?#xff0c;將不在環(huán)中的點(diǎn)都給處理掉。第一個(gè)答案就是所有環(huán)的長度加起來了。那么第二個(gè)答案怎么弄呢？如圖所示：

假如1的顏色是白色，2的顏色是白色，3的顏色是黑色的話，我們一開始在2,3放置機(jī)器人，那么第二個(gè)答案就是1，這樣的話是最大的。因此，我們在dfs找環(huán)的時(shí)候，就把這個(gè)環(huán)延伸出去的單鏈也處理一下，找出這些單鏈以及環(huán)上面的黑色的點(diǎn)。但是我們怎么判斷能不能在這個(gè)點(diǎn)上放置機(jī)器人呢？如圖所示：

dis數(shù)組就是dfs的過程中處理出來的，類似于樹中的深度。這個(gè)圖，我們可以看到第二個(gè)答案是2，在2或者4或者6，5放置的時(shí)候，這樣是最大的，我們可以發(fā)現(xiàn)，2和4和6對環(huán)的長度2取余都是0，他們不能同時(shí)放置機(jī)器人，而5對環(huán)的長度2取余是1,可以和2,4,6同時(shí)放置，也就是dis[i]%len這個(gè)數(shù)所代表的的點(diǎn)上只能放置一個(gè)（len代表環(huán)的長度）。上面那個(gè)圖怎樣處理出dis數(shù)組呢？我們肯定是從環(huán)上面的某一點(diǎn)出發(fā)，這樣的話，我們反向建圖，然后就可以處理出來了。
總結(jié)一下：一開始正反建圖，正向建圖是為了拓?fù)渑判?#xff0c;處理出環(huán)；反向建圖是為了從環(huán)上某一點(diǎn)出發(fā)，處理出dis數(shù)組，從而求出答案2.
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e6+100; string s1[maxx]; string s2[maxx]; vector<int> in[maxx],out[maxx],bck[maxx]; int vis[maxx],deg[maxx],dis[maxx],vis1[maxx]; int n,m;inline void init() {for(int i=0;i<=n*m+1;i++) deg[i]=0,vis[i]=0,in[i].clear(),out[i].clear(),dis[i]=0,vis1[i]=0,bck[i].clear(); } inline int get_pos(int x,int y) {return x*m+y; } inline void Topo() {queue<int> q;for(int i=0;i<n*m;i++) if(deg[i]==1) q.push(i);while(q.size()){int u=q.front();q.pop();deg[u]--;for(int i=0;i<in[u].size();i++){deg[in[u][i]]--;if(deg[in[u][i]]==1) q.push(in[u][i]);}} } inline void dfs(int u,int f,int step,int &num) {dis[u]=step;vis[u]=1;if(s1[u/m][u%m]=='0') bck[f].push_back(u);for(int i=0;i<out[u].size();i++){if(vis[out[u][i]])//這個(gè)點(diǎn)之前處理過，因?yàn)槭怯邢驁D，所以遇到之前處理過的點(diǎn)，說明在環(huán)上循環(huán)。那么當(dāng)前的步數(shù)，就是環(huán)的長度了。{num=step;continue;}dfs(out[u][i],f,step+1,num);} } int main() {int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();for(int i=0;i<n;i++) cin>>s1[i];for(int i=0;i<n;i++) cin>>s2[i];int tx,cx;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cx=get_pos(i,j);if(s2[i][j]=='R') tx=get_pos(i,j+1);if(s2[i][j]=='L') tx=get_pos(i,j-1);if(s2[i][j]=='U') tx=get_pos(i-1,j);if(s2[i][j]=='D') tx=get_pos(i+1,j);in[cx].push_back(tx);out[tx].push_back(cx);deg[cx]++,deg[tx]++;}}Topo();int ans1=0,ans2=0,num=0;for(int i=0;i<n*m;i++){if(deg[i]&&!vis[i]){dfs(i,i,1,num=0);ans1+=num;for(int j=0;j<bck[i].size();j++){if(vis1[dis[bck[i][j]]%num]==0){vis1[dis[bck[i][j]]%num]=1;ans2++;}}for(int j=0;j<bck[i].size();j++) vis1[dis[bck[i][j]]%num]=0;//在這里還要都?xì)w零，不要影響下次使用}}printf("%d %d\n",ans1,ans2);}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Robots on a Grid CodeForces - 1335F（拓扑排序+正反建图+判环）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。