译自 ROI 2014 Day2 T3. Здоровое питание
某大学的学生城规划为一个 的正方形网格，每个格子里都有一栋建筑。如果两栋建筑位于有公共边的相邻格子中，它们之间就有一条连通的通道。在正方形的左上角是学生宿舍，在右下角是教学楼。每栋建筑中（包括宿舍与教学楼）都设有一台自动售货机，每台售货机只出售一种食品，例如：仅售咖啡，或仅售肉馅饼等。学生每天都会从宿舍出发，沿着通道前往教学楼，并选择一条最短路径。
校方希望研究学生在行进过程中购买食品的多样性。对于每一台售货机 ，希望找到一条经过该售货机的最短路径，并且该路径上与 出售相同食品的售货机数量尽可能多。该数量称为售货机 的冗余度。已知售货机 位于宿舍内，而 位于教学楼内。
请编写程序，根据各售货机所售食品的信息，统计冗余度为 的售货机各有多少台。
