题解

题面描述

国家的领土被看作由 $n$ 行 $m$ 列构成的矩阵，每个单元格中都有一个部落，用小写字母表示，记为 $s_{i,j}$。
若同一部族的任意两个相邻（四相邻，即上下左右）的单元格直接连接，则这些单元格构成一个 亲密部落。
对于任意一个单元格，要求计算其所在的亲密部落与多少个不同的非本部族的部落（敌对部落）相邻。
输入给定 $n,\; m$ 以及 $n$ 行字符串，每行长度为 $m$，输出同样 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $(i,j)$ 单元格所在的亲密部落与多少个不同敌对部落相邻。

题目内容

某国的领土可以看作$n$行$m$列的矩阵，一共$n×m$个单元格，每一个单元格中都有一个部落。

我们使用$(i,j)$ 表示矩阵中从上往下数第$i$行和从左往右数第$j$列的单元格，里面的部族名为小写字母$s_{i,j}$

同一个部族的成员如果彼此相邻，那么他们更进一步的被称作亲密部落。更具体地，若存在这样两个单元格$(x,y)$ 和$(p,q)$，使得 $s_{x,y}$ =$s_{p,q}$且$|x-p|+|y-q| =1$，那么我们称他们属于同一个亲密部落。

现在小红想让你回答，对于任意$(i,j)$这个单元格上的部族，其所在亲密部落与多少个非自己部族的部族相邻。

在本题中，我们认为两个单元格$(x,y)$和$(p,q)$ 是相邻的,当且仅当$|x-p|+|y-q| =1$(四相邻)。

输入描述

第一行两个整数$n,m(1 ≦n,m≦500)$代表国家的领土大小。

此后$n$行，第i行输入一个长度为$m$，由小写字母组成的字符串$s_i$，代表第$i$行的部落分布。

输出描述

输出$n$行，每行$m$个整数，第$i$行第$j$个整数代表$(i,j)$所在部落存在多少不同的敌对部落。

样例1

输入

3 3
baa
aab
cac

输出

1 2 2 
2 2 2
1 2 2

说明

在这个样例中，以$(1,2)$这个单元格上的'$a$'部落为例，其所在的亲密部落共包含$5$个单元格，分别是$(1,2)，(1,3),(2,1),(2,2),(3,2)$。与'$b$'、'$a$'部落相邻 自5个