【题解】[NOIP模拟题]我要的幸福-C++

题目
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)没有被标记，那么这组数据是无解的。
如果有解，搜完一遍之后利用标记，用贪心输出。
其他的就很简单了。

代码

 #include<bits/stdc++.h>

 using namespace std;

 int a[][],n,m;

 bool vis[][];

 inline int read()

 {

     int data=;

     char ch=;

     while(ch<''||ch>'')

         ch=getchar();

     while(ch>=''&&ch<='')

         data=data*+ch-'',ch=getchar();

     return data;

 }

 struct node

 {

     int x,y;

 };

 bool in(int x,int y)

 {

     return <=x&&x<=n&&<=y&&y<=m;

 }

 void bfs(int x,int y)

 {

     int dir[][]={{-,},{,-}};

     queue<node> q;

     q.push((node){x,y});

     vis[x][y]=;

     while(!q.empty())

     {

         node now=q.front();

         q.pop();

         for(int i=;i<;i++)

         {

             int tx=now.x+dir[i][],ty=now.y+dir[i][];

             if(!vis[tx][ty]&&in(tx,ty)&&a[tx][ty]!=)

             {

                 q.push((node){tx,ty});

                 vis[tx][ty]=;

             }

         }

     }

     if(!vis[][])

     {

         cout<<"Oh,the life is too difficult!"<<endl;

         exit();

     }

 }

 int main()

 {

     n=read(),m=read();

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             a[i][j]=read();

     bfs(n,m);

     int x=,y=;

     while(x!=n||y!=m)

     {

         cout<<a[x][y]<<" ";

         if(!vis[x][y+]||y+>m)x++;

         else

             if(!vis[x+][y]||x+>n)y++;

             else

             {

                 if(a[x][y+]<a[x+][y])y++;

                 else x++;

             }

     }

     cout<<a[n][m]<<endl;

     return ;

 }

巴特西

【题解】[NOIP模拟题]我要的幸福-C++

最新文章

热门文章