【JZOJ1498】抓猫

题目大意：

一个 (n imes m) 的地方，每个格子都有方向，问最少要多少个装置从任意一点出发都会碰到装置。

正文：

如果格子连在一起成为一条路的话，其实只用求路的条数就行，考虑用并查集。

代码：

for (int i = 1; i <= n; ++i)
{
	for (int j = 0; j < m; ++j)
	{
		if (a[i][j - 1] == 'E')
			f[Get((i - 1) * m + j + 1)] 
				= Get((i - 1) * m + j);
		if (a[i][j + 1] == 'W')
			f[Get((i - 1) * m + j + 1)] 
				= Get((i - 1) * m + j + 2);
		if (a[i - 1][j] == 'S')
			f[Get((i - 1) * m + j + 1)] 
				= Get((i - 2) * m + j + 1);
		if (a[i + 1][j] == 'N')
			f[Get((i - 1) * m + j + 1)] 
				= Get(i * m + j + 1);
	}
}
for (int i = 1; i <= n * m; i++)
{
	if(f[i] == i)
		ans++;
}