P9957 [USACO20DEC] Stuck in a Rut B

题意归纳：

• 在一个被视为无限大二维方阵的农场中，每个方格都有草，有 $N$ 牛（$1$ $\le$ $N$ $\le$ $50$）初始分布在不同方格，且朝向为北面或东面。
• 牛行为：每小时每条牛执行以下操作之一：若当前方格草已被其他牛吃掉则停下；否则吃完当前方格草，并按朝向移动一格。若两条牛在移动中到达同一有草方格，它们分享草后继续按原方向移动。
• 问题求解：要求计算出每条牛最终吃到的草数量，部分牛可能因永远不会停下而吃到无限多草。

题目思路：

• 主要围绕牛之间的相互阻拦来计算移动方格数（即吃到草数量），没有直接处理方格中草是否已被吃掉的情况。
• 北为向上，东为向右。
• 创建结构体数组去保存每条牛的输入顺序、$x$ 坐标、$y$ 坐标、$x+y$、走的方格数量。
• 根据思路优化，将结构体数组进行排序，只有排序后处在前面的牛才有可能阻拦当前这条牛。
• 同一条斜线或者同一个方向的牛，肯定拦不住。
• 然后就是考虑两条牛方向不同的情况，并找到最短的方格数。

思路优化点：

为何需要两个 cmp 排序：

• cmp1 为根据 $x+y$ 进行排序；cmp2 为根据 $id$ 排序，即恢复初始输入顺序排序
• 在判断牛之间的阻拦关系时，按 $x+y$ 排序是一种巧妙的策略，它能帮助我们按照一种合理的顺序去依次检查每条牛是否会被其他牛阻拦。排序后，前面的牛在某种程度上更有可能阻拦后面的牛（基于它们在二维平面上相对位置的一种潜在关联性）。因为这个排序值综合考虑了横坐标和纵坐标，能大致反映牛在二维方阵中的一种相对先后顺序，方便后续依次遍历判断阻拦情况。
• 当按 $x + y$ 从大到小排序后，在遍历判断阻拦时，只需要考虑前面的牛对当前牛的阻拦情况即可（内层循环中 $j < i$），这样缩小了需要检查的范围，使得阻拦判断的逻辑更容易实现和理解。例如，如果不进行这样的排序，要判断一条牛是否会被其他所有牛阻拦，就需要进行更复杂的两两比较逻辑，而现在基于排序后的顺序依次检查，大大简化了代码实现过程中的比较和判断逻辑，提高了效率并且让代码结构更清晰。

Ac Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define _ read<int>()
template <class T>inline T read()
{
	T r=0,f=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-') f=-1;c=getchar();
	}
	while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=getchar();
	return f*r;
}
inline void out(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else out(x/10),putchar(x%10+'0');
}
int inf=2e9;
struct fish
{
	long long id, x, y, z, d;//x,y是初始位置，d是走的方格数量 
	char fx;//方向 
}a[100];
int n; 
bool cmp1(fish m, fish n)//按行列坐标之和进行排序排序
{
	return m.z > n.z;
}
bool cmp2(fish m, fish n)//把顺序调整回输入时候的顺序 
{
	return m.id < n.id; 
}
signed main()
{
	n=_;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		char c;
		cin>>c;//每头牛所在的x和y坐标不同 
		x=_,y=_;
		a[i]={i,x,y,x+y,inf,c};//无穷大 
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;i++)//遍历每一头牛 
	{
		for(int j=1;j<i;j++)//只有前面的点才有可能阻拦第i头牛
		{
			if(a[j].z == a[i].z || a[j].fx == a[i].fx) continue;//同一条斜线或者同一个方向的牛，肯定拦不住 
			if(a[i].fx == 'E' && a[j].fx == 'N')//i为向右的，j向上，然后找出最快拦住这条牛的步数 
			{
				if(a[i].y < a[j].y) continue;//i在j的下方，肯定拦不住 
				if(a[j].y+a[j].d > a[i].y) a[i].d = min(a[i].d, a[j].x-a[i].x);//j所在y加上移动步数如果大于i所在y，可以拦截 
			}
			else//i为向上，j为向右 
			{
				if(a[i].x < a[j].x) continue;//i在j的左方，肯定拦不住 
				if(a[j].x+a[j].d > a[i].x) a[i].d = min(a[i].d, a[j].y-a[i].y);//j所在x加上移动步数如果大于i所在x，可以拦截 
			}
		} 
	}
	sort(a+1,a+n+1,cmp2); 
	for(int i=1;i<=n;i++)
	{
		if(a[i].d==inf) puts("Infinity");
		else 
		{
			out(a[i].d);
			putchar('\n');
		}
	}
	return 0;
}