满足条件的一组导览点构成轴对齐直角三角形:直角顶点与另外两个顶点分别同行、同列,且三个格子上的字符恰好是 t、z、g 各一个。
因此可以先统计每个字符在每一行、每一列出现的次数,再枚举直角顶点所在格子:
t,则把「同行 z 与同列 g」以及「同行 g 与同列 z」两两配对;z 或 g,对另外两个字母做同样的配对。文博馆正在整理一块 n 行 m 列的展柜网格,每个格子上贴有一个小写字母标签。策展方案要求从网格中选出三个格子作为一组导览点:三个顶点上的字符必须恰好是 t、z、g 各一个。同时,这三个格子必须构成直角边分别沿水平和竖直方向的直角三角形,即三点中恰有两点同行、恰有两点同列。请统计有多少组满足条件的导览点。
约束:1≤n,m≤103。
第一行两个正整数 n 和 m,表示网格的行数和列数。 接下来 n 行,每行一个长度为 m 的小写字母字符串,表示网格的一行。 保证 1≤n,m≤103。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.