时间限制: 1 Sec 内存限制: 128 MB提交 状态
题目描述
在《明日方舟》游戏中，战场可以看作一个N*M的矩阵，矩阵中的每个点(i,j)有且只有两个值：若为0 ，则代表这个点是障碍；若为1，则代表这个点是平地。 有一位特殊的干员，她的攻击范围是战场中任意一个正方形的其中一条对角线，并且还必须满足以下条件： 1：该对角线上，每一个点都必须是平地； 2：该正方形除了该对角线之外的所有点都应为障碍； 只有满足上述两个条件，这位特殊的干员才能用她的火焰喷射器对该范围内的敌人进行攻击。 现在她想知道，自己在战场上最多能同时烧到几个点。
输入
第一行两个整数N,M，表示战场有N行，M列。 接下来N行，每行有M个数，第i行j列上的数表示战场上该位置的地形。
输出
一行一个整数，即该干员最多能烧到的点的数量。
样例输入 Copy
4 6 0 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0样例输出 Copy
3提示
样例1解释: 右上角的矩阵 1 0 0 0 1 0 0 0 1
今天准备写一篇高质量的文章，感谢大佬的代码和讲解
看到这道题，我的第一想法就是暴力的找每一个对角线和，然后再爆力的各种
然后，大佬说，是前缀和，emmm，见代码注释
1000 0100 0000 0001 这个答案是2 100 010 100
答案是2
好的，我没完过这个游戏，开始还理解错题意了.....
#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline")//优化 #include <bits/stdc++.h> using namespace std; int a[2550][2550]={0}; int d[2550][2550]={0}; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { scanf("%d",&a[i][j]); d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];//求前缀和 } } int max1=0; for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { int cnt=0; while(i+cnt<=n&&j+cnt<=m&&a[i][j]&&a[i+cnt][j+cnt])//正对角线 { int k1=d[i+cnt][j+cnt]-d[i-1][j+cnt]-d[i+cnt][j-1]+d[i-1][j-1];//(i+cnt,j+cnt)到(i,j)的前缀和 int k2=d[i+cnt-1][j+cnt-1]-d[i-1][j+cnt-1]-d[i+cnt-1][j-1]+d[i-1][j-1];//(i+cnt-1,j+cnt-1)到(i,j)的前缀和 if(k1==cnt+1&&k1-k2==1)//k1和k2相差1，并且(k1==cnt+1)说明k1是满足对角线之和，k2又增加一个，那肯定是啊a[i+cnt][j+cnt]这个元素,因为进入while的条件 { max1=max(max1,cnt+1);//更新答案 cnt++; } else break; } cnt=0; while(i+cnt<=n&&j-cnt>=1&&a[i][j]&&a[i+cnt][j-cnt])//对角线有两种，所以再来一个循环，原理同上，副对角线 { int k1=d[i+cnt][j]-d[i-1][j]-d[i+cnt][j-cnt-1]+d[i-1][j-1-cnt]; int k2=d[i+cnt-1][j]-d[i-1][j]-d[i+cnt-1][j-cnt]+d[i-1][j-cnt]; if(k1==cnt+1&&k1-k2==1) { max1=max(max1,cnt+1); cnt++; } else break; } } } cout<<max1<<endl; return 0; } /************************************************************** Problem: User: Language: C++ Result: 正确 Time:576 ms Memory:52824 kb ****************************************************************/
