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;
}

Download