Grid.cpp

/* Headers */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cctype> 
#include<algorithm>
#include<climits>
#include<vector>
/* define */
typedef std::pair<int,int> point;
/* consts */
const int MAXN = 2010;
using namespace std;
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==it)
            it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==it)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)  flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)  putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)    putch(q[top]);
    }
    inline void space(int x){
        if(!x)puts("");
        else putchar(' ');
    }
} 
using namespace FastIO;
/* defintions */
char word[MAXN][MAXN];
int n,m;
bool visited[MAXN][MAXN];
/* functions */
inline void init(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        cin>>word[i];
    }
}
inline void find_answer(){
    init();
    vector<point>v,nexts;
    for(v.push_back({0, 0}); !v.empty();v = nexts){
        point p=v.back();
        cout<<word[p.first][p.second];
        char another='z';
        for(point k : v){
            int x=1,y=0;
            for(int i=0;i<2;++i){
                swap(x,y);
                int dx=k.first+x;
                int dy=k.second+y;
                if(dx>=n||dy>=m)continue;
                another=min(another,word[dx][dy]);
            }
        }
        nexts.clear();
        for(point k : v){
            int x=1,y=0;
            for(int i=0;i<2;++i){
                swap(x,y);
                int dx=k.first+x;
                int dy=k.second+y;
                if(dx>=n||dy>=m)continue;
                if(visited[dx][dy])continue;
                if(word[dx][dy]==another){
                    nexts.push_back({dx,dy});
                    visited[dx][dy]=1;
                }
            }
        }
    }
}
int main(void){
    find_answer();
    space(0);
    return 0;
}