题目

Description

我要的幸福（happiness）

幸福/我要的幸福/渐渐清楚/梦想/理想/幻想/狂想/妄想/我只想坚持每一步/该走的方向/就算一路上/偶尔会沮丧/

生活是自己/选择的衣裳/幸福/我要的幸福/没有束缚/幸福/我要的幸福/在不远处

Description

Zyh相信自己想要的幸福在不远处。然而，zyh想要得到这幸福，还需要很长的一段路。Zyh坚持认为整个人生可以

抽象为一个n*m的棋盘。左上角的格子为(1,1)，右下角的格子为(n,m)。整个棋盘上的格子都有不同的事件，因为

生活的多姿多彩，事件的权值Aij都两两不同。不幸的是，在整个人生中有若干个极其黑暗的事件，它们的权值Aij

=0。更进一步说，对于Aij>0的事件，权值两两不同。Zyh站在人生的起点(1,1)，他想要走向人生的巅峰(n,m)。Zy

h认为人只能前进，即若Zyh站在(a,b)，他只能走向(a,b+1)或者(a+1,b)。并且Zyh认为黑暗的事件是绝对不可以触

碰的，因为一旦经历就会坠入万丈深渊。Zyh会将自己所经历的事件的权值依次写出，形成一个n+m-1的序列。Zyh

想知道其中字典序最小的序列是什么。若是人生过于艰难，没有一个合法序列，就输出"Oh,the life is too diff

icult!"，不包含引号。

Input

输入的第一行是两个正整数n和m。接着是n行m列的人生棋盘。

n<=1000 m<=1000 Aij<=1e9

Output

输入只有一列，如果存在合法序列，则为n+m-1个用一个空格隔开的权值。

否则就输出Oh,the life is too difficult!

Sample Input

3 3

1 3 4

7 9 0

5 6 8

Sample Output

1 3 9 6 8

思路

先从(n,m)出发搜一遍，如果最后(1,1)没有被标记，那么这组数据是无解的。

如果有解，搜完一遍之后利用标记，用贪心输出。

其他的就很简单了。

代码

1 #include
     
       2 using namespace std; 3 int a[1010][1010],n,m; 4 bool vis[1010][1010]; 5 inline int read() 6 { 7     int data=0; 8     char ch=0; 9     while(ch<'0'||ch>'9')10         ch=getchar();11     while(ch>='0'&&ch<='9')12         data=data*10+ch-'0',ch=getchar();13     return data;14 }15 struct node16 {17     int x,y;18 };19 bool in(int x,int y)20 {21     return 1<=x&&x<=n&&0<=y&&y<=m;22 }23 void bfs(int x,int y)24 {25       26     int dir[2][2]={
   {-1,0},{
   0,-1}};27     queue
      
        q;28     q.push((node){x,y});29     vis[x][y]=1;30     while(!q.empty())31     {32         node now=q.front();33         q.pop();34         for(int i=0;i<2;i++)35         {36             int tx=now.x+dir[i][0],ty=now.y+dir[i][1];37             if(!vis[tx][ty]&&in(tx,ty)&&a[tx][ty]!=0)38             {39                 q.push((node){tx,ty});40                 vis[tx][ty]=1;41                   42             }43         }44     }45     if(!vis[1][1])46     {47         cout<<"Oh,the life is too difficult!"<
       
        m)x++;63         else64             if(!vis[x+1][y]||x+1>n)y++;65             else66             {67                 if(a[x][y+1]