NKTABLE - NKTable
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 505
struct pos {
int x,y;
pos(){}
pos(const int &_x,const int &_y) {
x=_x;y=_y;
}
};
int a[MAX][MAX];
bool mv[MAX][MAX];
bool vs[MAX][MAX];
int m,n;
int res[2*MAX];
pos v[2][2*MAX];
int sz[2];
void init(void) {
scanf("%d",&m);
scanf("%d",&n);
int i,j;
for (i=1;i<=m;i=i+1)
for (j=1;j<=n;j=j+1)
scanf("%d",&a[i][j]);
}
void optimize(void) {
int i,j;
mv[m][n]=true;
vs[m][n]=false;
for (i=m;i>=1;i=i-1)
for (j=n-(i==m);j>=1;j=j-1) {
if (a[i][j]==2) mv[i][j]=false;
else mv[i][j]=mv[i+1][j]||mv[i][j+1];
vs[i][j]=false;
}
for (i=0;i<=m+1;i=i+1) {
mv[i][0]=false;
mv[i][n+1]=false;
}
for (i=0;i<=n+1;i=i+1) {
mv[0][i]=false;
mv[m+1][i]=false;
}
}
void BFS(void) {
int st,i,t,mval;
sz[1]=1;
v[1][1]=pos(1,1);
res[1]=a[1][1];
for (st=1;st<m+n-1;st=st+1) {
t=st%2;
mval=0;
for (i=1;i<=sz[t];i=i+1) {
if (mv[v[t][i].x+1][v[t][i].y] && mval<a[v[t][i].x+1][v[t][i].y]) mval=a[v[t][i].x+1][v[t][i].y];
if (mv[v[t][i].x][v[t][i].y+1] && mval<a[v[t][i].x][v[t][i].y+1]) mval=a[v[t][i].x][v[t][i].y+1];
}
res[st+1]=mval;
sz[1-t]=0;
for (i=1;i<=sz[t];i=i+1) {
if (!vs[v[t][i].x+1][v[t][i].y] && mv[v[t][i].x+1][v[t][i].y] && mval==a[v[t][i].x+1][v[t][i].y]) {
sz[1-t]++;
v[1-t][sz[1-t]]=pos(v[t][i].x+1,v[t][i].y);
vs[v[t][i].x+1][v[t][i].y]=true;
}
if (!vs[v[t][i].x][v[t][i].y+1] && mv[v[t][i].x][v[t][i].y+1] && mval==a[v[t][i].x][v[t][i].y+1]) {
sz[1-t]++;
v[1-t][sz[1-t]]=pos(v[t][i].x,v[t][i].y+1);
vs[v[t][i].x][v[t][i].y+1]=true;
}
}
}
for (st=1;st<m+n;st=st+1) printf("%d",res[st]);
}
int main(void) {
init();
optimize();
BFS();
return 0;
}