PROG-T1058: Longest

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;

bool board[N + 10][N + 10];
int mov[N + 10][N + 10][4];
int Q, row, col;

int main(){

    scanf("%d", &Q);
    for(int q = 1; q <= Q; ++q){
        scanf("%d %d", &row, &col);
        for(int i = 1; i <= row; ++i){
            for(int j = 1; j <= col; ++j){
                char tmpChar;
                scanf(" %c", &tmpChar);
                if(tmpChar == '1'){
                    board[i][j] = true;
                } else {
                    board[i][j] = false;
                }
            }
        }
        for(int i = 1; i <= row; ++i){
            int cnt = 0;
            for(int j = 1; j <= col; ++j){
                if(!board[i][j]){
                    cnt = -1;
                }
                mov[i][j][0] = cnt;
                ++cnt;
            }
            cnt = 0;
            for(int j = col; j >= 1; --j){
                if(!board[i][j]){
                    cnt = -1;
                }
                mov[i][j][1] = cnt;
                ++cnt;
            }
        }
        for(int i = 1; i <= col; ++i){
            int cnt = 0;
            for(int j = 1; j <= row; ++j){
                if(!board[j][i]){
                    cnt = -1;
                }
                mov[j][i][2] = cnt;
                ++cnt;
            }
            cnt = 0;
            for(int j = row; j >= 1; --j){
                if(!board[j][i]){
                    cnt = -1;
                }
                mov[j][i][3] = cnt;
                ++cnt;
            }
        }

        int mx = 0;
        for(int i = 1; i <= row; ++i){
            for(int j = 1; j <= col; ++j){
                if(board[i][j]){
                    mx = max(mx, max(mov[i][j][0], mov[i][j][1]) + max(mov[i][j][2], mov[i][j][3]));
                }
            }
        }
        cout << mx + 1 << "\n";
    }

    return 0;
}