这题说的是给了一个n*m的网格，然后每个格子的点事黑色的或者是白色的然后每个点如图所示
然后只能用白点和图中给出的边建立三角形然后询问三角形的个数有多少个，这样说每个三角形的边必须是图中有的边，然后三角形的边上的点必须全部为白色的点然后计算这样能组成多少个三角形，先对每个点处理好他8个方向所能到达最大的长度，这里花了n*m*4的时间然后去判断每个点所能到达的最多多少个三角形时间为400*400*400然后得解
#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> using namespace std; const int MAX_N = 405; int len[MAX_N][MAX_N][8]; char map[MAX_N][MAX_N]; __int64 ans=0; int n,m; void init(){ for(int i=1; i<=n; i++){ for(int j=1 ; j<=m; ++j ) if(map[i][j]=='1'){ len[i][j][0]=0; len[i][j][1]=0; len[i][j][7]=0; }else{ len[i][j][0]=len[i-1][j-1][0]+1; len[i][j][1]=len[i-1][j][1]+1; len[i][j][7]=len[i][j-1][7]+1; } for(int j=m; j>0; --j) if(map[i][j]=='1'){ len[i][j][2]=0; len[i][j][3]=0; }else{ len[i][j][2]=len[i-1][j+1][2]+1; len[i][j][3]=len[i][j+1][3]+1; } } for(int i=n; i>0; i--){ for(int j = 1; j<=m; ++j ) if(map[i][j]=='1') { len[i][j][6]=0; len[i][j][5]=0; }else{ len[i][j][6]=len[i+1][j-1][6]+1; len[i][j][5]=len[i+1][j][5]+1; } for(int j=m; j>0; --j) if(map[i][j]=='1'){ len[i][j][4]=0; }else{ len[i][j][4]=len[i+1][j+1][4]+1; } } } int pC(int a,int b,int c){ if(a>=b&&b>=c) return b; if(a>=c&&c>=b) return c; if(b>=a&&a>=c) return a; if(b>=c&&c>=a) return c; if(c>=a&&a>=b) return a; if(c>=b&&b>=a) return b; } void solve1(int x,int y,int L){ for(int k= 1 ; k< L; ++k) { if(x-k<1) break; if(len[x][y][1]>k&&len[x][y][7]>k&&len[x-k][y][6]>k) ans++; if(len[x][y][1]>k&&len[x][y][3]>k&&len[x-k][y][4]>k) ans++; if(len[x][y][7]>k&&len[x][y][3]>k&&len[x-k][y][6]>k&&len[x-k][y][4]>k) ans++; } } void solve2(int x,int y,int L){ for(int k=1; k<L; k++){ if(y+k>m) break; if(len[x][y][3]>k && len[x][y][5]>k && len[x][y+k][6]>k) ans++; if(len[x][y][1]>k && len[x][y][5]>k && len[x][y+k][0]>k && len[x][y+k][6]>k) ans++; } } void solve3(int x,int y,int L){ for(int k =1; k<L ;k++){ if(x+k>n) break; if(len[x][y][7]>k && len[x][y][5]>k && len[x+k][y][0]>k) ans++; if(len[x][y][7]>k&& len[x][y][3]>k && len[x+k][y][0]>k && len[x+k][y][2]>k ) ans++; } } void solve4(int x,int y,int L){ for(int k=1; k<L ; ++k) { if(y-k<1) break; if(len[x][y][1]>k&&len[x][y][5]>k&&len[x][y-k][2]>k&&len[x][y-k][4]>k) ans++; } } int main() { while(scanf("%d%d",&n,&m)==2){ ans=0; for(int i=1; i<=n; ++i) scanf("%s",map[i]+1); memset(len,0,sizeof(len)); init(); for(int i=1; i<=n; i++ ){ for(int j=1; j<=m; ++j){ int L = pC(len[i][j][7],len[i][j][1],len[i][j][3]); solve1(i,j,L); L = pC(len[i][j][1],len[i][j][3],len[i][j][5]); solve2(i,j,L); L = pC(len[i][j][3],len[i][j][5],len[i][j][7]); solve3(i,j,L); L = pC(len[i][j][1],len[i][j][5],len[i][j][7]); solve4(i,j,L); } } printf("%I64d ",ans); } return 0; }