PROG-1058: Longest

#include <bits/stdc++.h>
using namespace std;
int n,m;
char ar[1001][1001];
int up[1001][1001],l[1001][1001];
int down[1002][1002],r[1002][1002];
int find_max(int a,int b,int c,int d,int e,int f,int g){
    return max(a,max(b,max(c,max(d,max(e,max(f,g))))));
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                up[i][j]=0;
                down[i][j]=0;
                l[i][j]=0;
                r[i][j]=0;
                scanf(" %c",&ar[i][j]);
                if(ar[i][j]=='1'){
                    up[i][j]=up[i-1][j]+1;
                    l[i][j]=l[i][j-1]+1;
                }
            }
        }
        for(int j=1;j<=m+1;j++) down[n+1][j]=0;
        for(int i=1;i<=n+1;i++) r[i][m+1]=0;

        int mx=0;
        for(int i=n;i>=1;i--){
            for(int j=m;j>=1;j--){
                if(ar[i][j]=='0') continue;
                int up_down,left_right,up_right,up_left,down_right,down_left;

                down[i][j]=down[i+1][j]+1;
                r[i][j]=r[i][j+1]+1;

                up_down=1+up[i-1][j]+down[i+1][j];
                left_right=1+l[i][j-1]+r[i][j+1];
                up_right=1+up[i-1][j]+r[i][j+1];
                up_left=1+up[i-1][j]+l[i][j-1];
                down_right=1+r[i][j+1]+down[i+1][j];
                down_left=1+l[i][j-1]+down[i+1][j];

                mx=find_max(mx,up_down,left_right,up_right,up_left,down_right,down_left);
            }
        }
        printf("%d\n",mx);
    }

    return 0;
}