(算是dp吧) 小茗的魔法阵（fzu 2225）

http://acm.fzu.edu.cn/problem.php?pid=2225

Problem Description

在打败了易基•普罗布朗、诺姆•普罗布朗之后，小茗同学开始挑战哈德•普罗布朗。

一番交战之后，哈德展开了一大波攻击。小茗同学为了抵御攻击，一边放魔法阵一边放魔法阵，然后他也不知道自己一共放了几个魔法阵。回收魔法阵是需要花费时间的，为了抵御下一波攻击，小茗同学需要知道自己共放了几个魔法阵，由于情况紧急，这个任务需要由你来完成。

魔法阵是三角形△的，比如

.............

.x..x....x...

...xxx..x.x..

.......xxxxx.

.............

以上都认为是魔法阵。

（即：三角形三个顶点为(i,j),(i+k,j-k),(i+k,j+k)，边上均为’x’。三角形中间的元素没有要求。一个’x’可以同时属于多个魔法阵。单个’x’也算一个魔法阵。）

场地可以认为是一个N×M的矩形，每个位置上为’.’表示没有东西，或’x’表示有魔法阵。

Input

第一行是一个整数T(T<=10)，表示共有T组测试数据。

每组数据的第一行包含两个整数N M(N,M≤1000)，表示矩阵大小。

接下来N行，每行M个字母为‘.’或者‘x’。

Output

每组数据输出独占一行，输出格式为”Case #x: y”，x从1开始，表示数据组号，y表示相应的魔法阵的数量。

Sample Input

1 3 3 .x. xxx ...

Sample Output

Case #1: 5

Source

FOJ有奖月赛-2016年4月（校赛热身赛）

#include <cstdio>

#include <queue>

#include <stack>

#include <cmath>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define lson 2*root

#define rson 2*root+1

#define met(a,b) (memset(a,b,sizeof(a)))

typedef long long LL;

const LL mod = ;

const LL INF= 1e9+;

const int N = ;

char s[N][N];

int dp[N][N], dL[N][N], dR[N][N];

///右边，左下，右下记录连续的， 最后再判断能够增加的大三角形，代码还是很容易能看懂的

int main()

{

    int T, iCase=;

    scanf("%d", &T);

    while(T--)

    {

        int i, j, k, n, m, cnt=;

        scanf("%d%d", &n, &m);

        met(s, );

        met(dp, );

        met(dL, );

        met(dR, );

        for(i=; i<=n; i++)

        {

            scanf("%s", s[i]+);

            for(j=; j<=m; j++)

            {

                if(s[i][j]=='x')

                {

                    cnt++;

                    dp[i][j] = dL[i][j] = dR[i][j] = ;

                }

            }

        }

        for(i=n; i>=; i--)

        for(j=m; j>=; j--)

        {

            if(dp[i][j])

                dp[i][j] += dp[i][j+];

            if(dL[i][j])

                dL[i][j] += dL[i+][j-];

            if(dR[i][j])

                dR[i][j] += dR[i+][j+];

        }

        for(i=; i<=n; i++)

        for(j=; j<=m; j++)

        {

            for(k=; k<=min(dL[i][j], dR[i][j]); k++)

            {

                if(dp[i+k][j-k]>=*k+)

                    cnt++;

            }

        }

        printf("Case #%d: %d\n", iCase++, cnt);

    }

    return ;

}