Codeforces 1335F - Robots on a Grid(배가)

Description
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
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.
제목의 대의.
n*m의 격자가 있고 격자마다 색깔이 있고 격자마다 전진하는 방향이 있다. 이런 격자에 로봇을 배치해야 한다. 로봇은 격자의 방향에 따라 걷는다. 격자마다 한 걸음도 걷지 않기 때문에 로봇이 충돌하지 않을 것이다. 여러 로봇이 같은 격자에 도착하는 동시에 초기 상태의 로봇이 있는 검은색 격자 수를 최대한 많이 해야 한다.배치 가능한 최대 로봇 수량과 초기 점령한 최대 검은색 칸 수량 출력
만약 두 로봇이 충돌한다면 어느 한 걸음 뒤에 같은 칸이 있다는 것을 설명한다.가장 많이 n*m보(이 격자에서 가장 큰 고리는 n*m)를 걷는다면 n*m보를 걷고 모든 격자를 걷는 로봇이 걸어갈 격자입니다.한 번 훑어보면 만약에 어떤 칸 n*m 걸음이 검은색 칸에 도달하면 기계 인원수와 검은색 칸수에 모두 기여를 할 수 있다. 만약에 어떤 칸 n*m 걸음이 흰색 칸에 도달하면 기계 인원수에 기여를 할 수 있다... 누적 출력 수조가 열리지 않고 1차원 수조로 전환해야 한다. t도 매우 크다. 직접적으로memset으로 0을 설치하면 0으로 순환치울 수 없다.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int fa[maxn][22],c[maxn];
char s[maxn];
int bla[maxn],whi[maxn];
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf("%s",s+1);
            for(int j=1;j<=m;++j)c[(i-1)*m+j]=s[j]-'0';
        }
        for(int i=1;i<=n;++i){
            scanf("%s",s+1);
            for(int j=1;j<=m;++j){
                int to=(i-1)*m+j;
                if(s[j]=='L')--to;
                else if(s[j]=='R')++to;
                else if(s[j]=='U')to-=m;
                else to+=m;
                fa[(i-1)*m+j][0]=to;
            }
        }
        n*=m;
        for(int j=1;j<=20;++j){
            for(int i=1;i<=n;++i){
                fa[i][j]=fa[fa[i][j-1]][j-1];
            }
        }
        int all=0,ans=0;
        for(int i=1;i<=n;++i){
            int to=i,y=n;
            for(int j=20;j>=0;--j)
                if(y&(1<<j))to=fa[to][j];
            if(c[i]==0)bla[to]=1;
            else whi[to]=1;
        }
        for(int i=1;i<=n;++i){
            if(bla[i]==1)++all,++ans;
            else if(whi[i]==1)++all;
        }
        for(int i=1;i<=n;++i)bla[i]=0,whi[i]=0;
        printf("%d %d
",all,ans);
    }
    return 0;
}