题目链接

题面：

题意：
给定一个 n ∗ m n*m n∗m 的方格矩阵，方格内有数。
方格的坐标为 1 − n , 1 − m 1-n,1-m 1−n,1−m，边界的坐标为 0 − n , 0 − m 0-n,0-m 0−n,0−m。
边界上给定一点，然后给定一个字符串 S S S，这一点按照字符串移动的轨迹是一个简单的多边形。
问这个多边形中本质不同的数有多少个。

题解：
因为这个题的LRUD的问题，我们坐标系建立为x轴为横轴，正方向向右；y轴为纵轴，正方向向上。
我们可以把边界点看作坐标系中的点，把方格点看作形成的单位正方形。


极限数据为 4 n − > n 2 4n->n^2 4n−>n2得到 S 4 n ∗ n 2 = S n 4 \frac{S}{4n}*n^2=\frac{Sn}{4} 4nS​∗n2=4Sn​

我们处理出每个点向y轴负方向的射线经过多少次边界，如果经过奇数次，说明在多边形里面；如果经过偶数次，说明在多边形外面。

我们的桶数组直接每次标记++即可，这样就不用初始化了。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)>(y)?(y):(x)
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-1;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=405;
const int maxp=1100;
const int maxm=4000100;
const int up=100000;

int cnt[maxn*maxn],a[maxn][maxn],pos=0,ans;
bool ha[maxn][maxn];
char str[maxm];

int main(void)
{
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        }
        int xmax=0,xmin=n,ymax=0,ymin=m;
        int x,y;
        for(int k=1;k<=q;k++)
        {
            scanf("%d%d%s",&x,&y,str+1);
            xmax=0,xmin=n,ymax=0,ymin=m;
            for(int i=1;str[i];i++)
            {
                if(str[i]=='L')
                {
                    ha[x][y+1]^=1;
                    x--;
                }
                else if(str[i]=='R')
                {
                    x++;
                    ha[x][y+1]^=1;
                }
                else if(str[i]=='U') y++;
                else if(str[i]=='D') y--;
                xmax=max(xmax,x);
                xmin=min(xmin,x);
                ymax=max(ymax,y);
                ymin=min(ymin,y);
            }
            pos++;
            ans=0;
            for(int i=xmin;i<=xmax;i++)
            {
                for(int j=ymin;j<=ymax;j++)
                {
                    ha[i][j]^=ha[i][j-1];
                    if(ha[i][j])
                    {
                        if(cnt[a[i][j]]!=pos)
                        {
                            cnt[a[i][j]]=pos;
                            ans++;
                        }
                    }
                }
            }
            printf("%d\n",ans);
            for(int i=xmin;i<=xmax;i++)
            {
                for(int j=ymin+1;j<=ymax+1;j++)
                    ha[i][j]=false;
            }

        }
    }
    return 0;
}