题目链接：http://codeforces.com/problemset/problem/435/D

题意：求三角形个数，三个点必须的白点上，而且三条边必须是横线，竖线或对角线，三条边上不同意出现黑点。

解法：dp，计算以每一个点为三角形左下角的个数，当*同拥有8种形状。为了O(1)查询某段横线竖线和对角线是否有黑点，须要预处理各个方向的黑点数量；

代码：

/******************************************************

* @author:xiefubao

*******************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <stack>

#include <string.h>

//freopen ("in.txt" , "r" , stdin);

using namespace std;

#define eps 1e-8

#define zero(_) (abs(_)<=eps)

const double pi=acos(-1.0);

typedef long long LL;

const int Max=100010;

const int INF=1e9+7;

LL ans=0;

char s[410][410];

int heng[410][410];

int shu[410][410];

int xie1[410][410];

int xie2[410][410];

int n,m;

bool OK1(int i,int j,int k)

{

    return xie2[i][j]-xie2[i-k][j+k]==0;

}

bool OK2(int i,int j,int k)

{

    return heng[i][j+k]-heng[i][j]==0;

}

bool OK3(int i,int j,int k)

{

    return xie1[i][j]-xie1[i-k][j-k]==0;

}

bool OK4(int i,int j,int k)

{

    return shu[i][j]-shu[i-k][j]==0;

}

bool OK(int i,int j)

{

    return i>=0&&i<n&&j>=0&&j<m;

}

int main()

{

    cin>>n>>m;

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

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

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

    {

        heng[i][0]=(s[i][0]=='1');

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

            heng[i][j]=heng[i][j-1]+(s[i][j]=='1');

    }

    for(int i=0; i<m; i++)

    {

        shu[0][i]=(s[0][i]=='1');

        for(int j=1; j<n; j++)

            shu[j][i]=shu[j-1][i]+(s[j][i]=='1');

    }

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

    {

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

        {

            xie1[i][j]=(s[i][j]=='1');

            if(OK(i-1,j-1))

                xie1[i][j]+=xie1[i-1][j-1];

        }

    }

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

    {

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

        {

            xie2[i][j]=(s[i][j]=='1');

            if(OK(i-1,j+1))

                xie2[i][j]+=xie2[i-1][j+1];

        }

    }

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=min(i,j); k++)

            {

                if(s[i][j-k]=='0'&&s[i-k][j]=='0'&&OK1(i,j-k,k))

                    ans++;

                if(s[i][j-k]=='1'||s[i-k][j]=='1')

                    break;

            }

        }

    //cout<<ans<<endl;

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=min(i,j); k++)

            {

                if(s[i][j-k]=='0'&&s[i-k][j-k]=='0'&&OK4(i,j-k,k))

                    ans++;

                if(s[i][j-k]=='1'||s[i-k][j-k]=='1')

                    break;

            }

        }

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=min(i,j); k++)

            {

                if(s[i-k][j]=='0'&&s[i-k][j-k]=='0'&&OK2(i-k,j-k,k))

                    ans++;

                if(s[i-k][j]=='1'||s[i-k][j-k]=='1')

                    break;

            }

        }

    //cout<<ans<<endl;

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=min(i,m-j-1); k++)

            {

                if(s[i-k][j]=='0'&&s[i-k][j+k]=='0'&&OK2(i-k,j,k))

                    ans++;

                if(s[i-k][j]=='1'||s[i-k][j+k]=='1')

                    break;

            }

        }

    //cout<<ans<<endl;

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=min(j,min(i,m-j-1)); k++)

            {

                if(s[i-k][j-k]=='0'&&s[i-k][j+k]=='0'&&OK2(i-k,j-k,2*k))

                    ans++;

                if(s[i-k][j-k]=='1'||s[i-k][j+k]=='1')

                    break;

            }

        }

    //cout<<ans<<endl;

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=j&&2*k<=i; k++)

            {

                if(s[i-k][j-k]=='0'&&s[i-2*k][j]=='0'&&s[i-2*k+1][j]=='0'&&OK1(i-k,j-k,k))

                    ans++;

                if(s[i-k][j-k]=='1'||s[i-2*k][j]=='1'||s[i-2*k+1][j]=='1')

                    break;

            }

        }

    //cout<<ans<<endl;

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=m-1-j&&2*k<=i; k++)

            {

                if(s[i-k][j+k]=='0'&&s[i-2*k][j]=='0'&&s[i-2*k+1][j]=='0'&&OK3(i-k,j+k,k))

                    ans++;

                if(s[i-k][j+k]=='1'||s[i-2*k][j]=='1'||s[i-2*k+1][j]=='1')

                    break;

            }

        }

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

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

        {

            if(s[i][j]=='1') continue;

            for(int k=1; k<=j&&2*k<=j; k++)

            {

                if(s[i][j-2*k]=='0'&&s[i][j-2*k+1]=='0'&&s[i-k][j-k]=='0'&&OK1(i,j-2*k,k))

                    ans++;

                if(s[i][j-2*k]=='1'||s[i][j-2*k+1]=='1'||s[i-k][j-k]=='1')

                    break;

            }

        }

    cout<<ans<<endl;

    return 0;

}