OJ题号:ZHOJ1297
思路:搜索。
先预处理注定不能走的路径,然后dfs可以走的路径。
#pragma GCC optimize ("O2")
#include<cstdio>
#include<cstdlib>
#include<cctype>
const int N=;
int n,m,len,a[N][N]={{}},path[N<<];
int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
void printpath() {
for(int i=;i<len;i++) printf("%d ",path[i]);
puts("");
}
void dfs(int x,int y) {
if(!a[x][y]) return;
path[x+y]=a[x][y];
if((x+y+)==len) {
printpath();
exit();
}
if((x+)==n) {
dfs(x,y+);
return;
}
if((y+)==m) {
dfs(x+,y);
return;
}
if(a[x+][y]<a[x][y+]) {
dfs(x+,y);
dfs(x,y+);
}
else {
dfs(x,y+);
dfs(x+,y);
}
}
int main() {
n=getint();
m=getint();
len=n+m-;
for(register int i=;i<n;i++) {
for(register int j=;j<m;j++) {
a[i][j]=getint();
}
}
for(register int i=n-;i>=;i--) {
for(register int j=m-;j>=;j--) {
if((i==(n-))&&(j==(m-))) continue;
if(!a[i+][j]&&!a[i][j+]) a[i][j]=;
}
}
if(a[n-][m-]) dfs(,);
puts("Oh,the life is too difficult!");
return ;
}