题解

本题使用坐标变换 + 哈希表求解周期性路径覆盖的网格计数问题。

算法思路：

1. 问题分析：

   • 执行 $m$ 次移动指令后，最终位移为 $(xf, yf)$
   • 需要统计经过 $n$ 轮（$n$ 次执行完整指令）后，形成的 $1 \times 1$ 网格数量
   • 网格的四个角都必须被路径经过

2. 特殊情况：无周期性（$xf = 0, yf = 0$）：

   • 路径最终回到原点，不会扩展
   • 直接统计单次执行指令经过的所有点
   • 检查每个点及其右上角相邻点是否都被访问，计数满足条件的网格

3. 坐标归一化：

   • 如果 $xf = 0$ 但 $yf \neq 0$，交换 $x$ 和 $y$ 坐标
   • 如果 $xf < 0$，翻转 $x$ 方向
   • 如果 $yf < 0$，翻转 $y$ 方向
   • 确保 $xf > 0$

4. 周期性坐标转换：

   • 对于点 $(x, y)$，定义周期内坐标：$cw(x, y) = (x \bmod xf, y - \lfloor x / xf \rfloor \times yf)$
   • 使用哈希表 ff 记录每个周期内坐标在哪一轮首次出现
   • 使用哈希表 af 记录每个实际坐标在哪一轮可达

5. 网格统计：

   • 对于每个可能形成网格的左下角 $(x, y)$
   • 检查四个角 $(x, y), (x+1, y), (x, y+1), (x+1, y+1)$ 是否都可达
   • 计算这四个点的最大可达轮数 $maxRound$
   • 使用周期性映射优化计数，避免重复统计

6. 答案计算：

   • 对于每个满足条件的网格，计算其在 $[1, n]$ 范围内的出现次数
   • 累加所有网格的贡献

时间复杂度：$O(m + |visited|)$，其中 $|visited|$ 是访问过的不同坐标数量。

这是一道综合性较强的几何问题，需要理解周期性坐标变换和哈希表的应用。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int n,m,xf,yf,fx,fy,p[20][20];
long long d;
string a;
map<pair<int,int>,int> caf,af,ff,fd;
pair<int,int> cw(int x,int y){
	return {x%xf,y-x/xf*yf};
}
void cr(int x,int y){
	if(af.find({x,y})!=af.end())
		return;
	auto fz=ff.find(cw(x,y));
	if(fz==ff.end())
		return;
	af[{x,y}]=x/xf-(*fz).second+1;
}
int main(){
	cin>>n>>m>>a;
	for(auto i:a){
		if(i=='E')
			xf++;
		if(i=='W')
			xf--;
		if(i=='N')
			yf++;
		if(i=='S')
			yf--; 
	}
	if(xf==0 && yf==0){
		for(auto i:a){
			if(i=='E')
				fx++;
			if(i=='W')
				fx--;
			if(i=='N')
				fy++;
			if(i=='S')
				fy--;
			af[{fx,fy}];
		}
		for(auto ii:af){
			auto i=ii.first;
			if(af.find({i.first+1,i.second})!=af.end() && af.find({i.first,i.second+1})!=af.end() && af.find({i.first+1,i.second+1})!=af.end())
				d++;
		}
		cout<<d;
		return 0;
	}
	if(xf==0){
		swap(xf,yf);
		for(auto &i:a){
			if(i=='E')
				i='N';
			else if(i=='N')
				i='E';
			if(i=='W')
				i='S';
			else if(i=='S')
				i='W';
		}
	}
	if(xf<0){
		xf=-xf;
		for(auto &i:a){
			if(i=='E')
				i='W';
			else if(i=='W')
				i='E';
		}
	}
	if(yf<0){
		yf=-yf;
		for(auto &i:a){
			if(i=='N')
				i='S';
			else if(i=='S')
				i='N';
		}
	}
	fx=200000;
	fy=200000;
	af[{fx,fy}]=1;
	for(auto i:a){
		if(i=='E')
			fx++;
		if(i=='W')
			fx--;
		if(i=='N')
			fy++;
		if(i=='S')
			fy--;
		caf[{fx,fy}]=1;
		for(int j1=-1;j1<=1;j1++)
			for(int j2=-1;j2<=1;j2++)
				caf[{fx+j1,fy+j2}];
	}
	for(auto ii:caf){
		auto i=ii.first;
		if(ii.second)
			ff[cw(i.first,i.second)]=i.first/xf;
		cr(i.first,i.second);
	}
	for(auto ii:af){
		auto i=ii.first;
		if(af.find({i.first+1,i.second})!=af.end() && af.find({i.first,i.second+1})!=af.end() && af.find({i.first+1,i.second+1})!=af.end())
			fd[i]=max(max(af[i],af[{i.first+1,i.second}]),max(af[{i.first,i.second+1}],af[{i.first+1,i.second+1}]));
	}
	ff.clear();
	for(auto ii:fd){
		auto i=ii.first;
		if(ff.find(cw(i.first,i.second))==ff.end())
			ff[cw(i.first,i.second)]=2*m;
		int &mn=ff[cw(i.first,i.second)];
		d+=max(0,min(m+1,mn+i.first/xf)-ii.second);
		mn=min(mn,ii.second-i.first/xf);
	}
	cout<<d;
	return 0;
}