SP4177 HERDING - Herding

不得了！城市里出现了一些流浪猫，作为城市的捕猫员，你接到了一项重要的任务：抓回所有的猫。这正是测试你最新发明的猫陷阱的好机会——这个陷阱可以保证抓住进入城市任意正方形区域内的猫。 幸运的是，有位世界一流的猫心理学家与你合作，他有能力预测猫在某个正方形区域内会向哪个方向（北、东、南或西）移动。虽然这个信息很有用，但你仍然不知道每只猫现在具体在哪个位置。 为了向城市管理者证明你的方法具有成本效益，你需要努力减少使用陷阱的数量到最少。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$（$1 \le n, m \le 1000$），表示城市是一个 $n \times m$ 的网格，每个方格代表一个正方形子区域。接下来的 $n$ 行中，每行有一个长度为 $m$ 的字符串，由字母 'N'、'E'、'S'、'W' 组成，分别表示北、东、南和西。这些字母表示猫在该方格中会选择的移动方向。猫心理学家保证猫永远不会离开城市之外。

输出需要使用的最少陷阱数量。 **本翻译由 AI 自动生成**