【题目地址】
【题目大意】
在一个m*n的矩阵里，给出一些国际象棋中的王，让你求出所有王对（。。。就是那些点对）之间最小到达步数的和。
【算法分析】
设
LU[i][j]表示以（i，j）为右下角的这个矩形内的所有的王跳到(i，j)这个位置一共跳了多少步。
LS[i][j]表示以（i，j）为右下角的这个矩形内的所有的王的数目。
RU[i][j]和RS[i][j]同上。
UU[i][j]表示以从(1，j)到（i，j）这一路下来的王跳到（i，j）一共跳的步数。
US[i][j]表示以从(1，j)到（i，j）这一路下来一共有多少个王。
然后就是设法维护一下，像dp一样，并不是很难。
【CODE】
#include <cstdio>
#include <cstdlib>
#include <cstring>
int m,n;
long long LU[1005][1005],RU[1005][1005],UU[1005][1005];
int LS[1005][1005],RS[1005][1005],US[1005][1005];
char c[1005][1005];
void init(){
scanf("%d%d",&m,&n);
for (int i=1;i<=m;i++)
scanf("%s",&c[i][1]);
}
void solve(){
int i,j;
memset(LS,0,sizeof(LS));
memset(RS,0,sizeof(RS));
memset(LU,0,sizeof(LU));
memset(RU,0,sizeof(RU));
long long ans=0;
for (i=1;i<=m;i++){
for (j=1;j<=n;j++){
LU[i][j]=LU[i][j-1]+LS[i][j-1];
LS[i][j]=LS[i][j-1];
if (c[i][j]=='M'){
LS[i][j]++;
ans+=LU[i][j];
}
}
for (j=n;j>=1;j--){
RU[i][j]=RU[i][j+1]+RS[i][j+1];
RS[i][j]=RS[i][j+1];
if (c[i][j]=='M') RS[i][j]++;
}
for (j=1;j<=n;j++){
UU[i][j]=UU[i-1][j]+US[i-1][j];
US[i][j]=US[i-1][j];
if (c[i][j]=='M'){
US[i][j]++;
ans+=UU[i][j];
}
}
for (j=1;j<=n;j++){
if (c[i][j]=='M')
ans+=LU[i-1][j-1]+LS[i-1][j-1]+RU[i-1][j+1]+RS[i-1][j+1];
LU[i][j]+=LU[i-1][j-1]+LS[i-1][j-1]+UU[i-1][j]+US[i-1][j];
LS[i][j]+=LS[i-1][j-1]+US[i-1][j];
RU[i][j]+=RU[i-1][j+1]+RS[i-1][j+1]+UU[i-1][j]+US[i-1][j];
RS[i][j]+=RS[i-1][j+1]+US[i-1][j];
}
}
printf("%lld",ans);
}
int main(){
init();
solve();
printf(" ");
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
if (c[i][j]=='M') c[i][j]='.';
if (c[i][j]=='S') c[i][j]='M';
}
solve();
printf("\n");
}
