View Code of Problem 3602

#include <iostream>
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
#include <algorithm>
using namespace std;

int n,m,pos,sx,sy;
char ss[1002][1002];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int vis[1002][1002],que[1002];
int isin(int x,int y)
 {
    return x>=0&&x<n&&y>=0&&y<m;
 }
void bfs(int x,int y)
{
    int  pre,last,tempx,tempy;
    memset(que,0,sizeof(que));
    pre=last=0;
    que[last++]=x;
    que[last++]=y;
    while(pre<last)
    {
        tempx=que[pre++];
        tempy=que[pre++];
        for(int i=0;i<4;i++)
        {
            int nx=tempx+dir[i][0];
            int ny=tempy+dir[i][1];
            if(!isin(nx,ny)||vis[nx][ny])  continue;
            vis[nx][ny]=1;
            if(ss[nx][ny]=='0') {
                que[last++]=nx;
                que[last++]=ny;
            }
            if(sx+sy<nx+ny){
                sx=nx;sy=ny;
            }
        }
    }
}
int main() {
    int kase;
    scanf("%d",&kase);
    while(kase--) {
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; ++i) scanf("%s",ss[i]);
        sx = sy = 0;
        memset(vis,false,sizeof vis);
        vis[0][0] = 1;
        if(ss[0][0] == '0') bfs(0,0);
        if(ss[sx][sy] == '0') puts("0");
        else {
            bool nowflag = false;
            putchar('1');
            for(int i = sx + sy; i < n + m - 2; ++i){
                bool flag = false;
                for(int k = 0; k <= i; ++k){
                    int x = k;
                    int y = i - k;
                    if(!isin(x,y) || !vis[x][y]) continue;
                    if(nowflag && ss[x][y] == '1') continue;
                    for(int j = 0; j < 2; ++j){
                        int nx = x + dir[j][0];
                        int ny = y + dir[j][1];
                        if(!isin(nx,ny)) continue;
                        vis[nx][ny] = true;
                        if(ss[nx][ny] == '0') flag = true;
                    }
                }
                nowflag = flag;
                putchar(flag?'0':'1');
            }
            putchar('\n');
        }
    }
    return 0;
}