1.题意简述
\(Zyh\) 相信自己想要的幸福在不远处。然而，\(zyh\) 想要得到这幸福，还需要很长的一段路。
\(Zyh\) 坚持认为整个人生可以抽象为一个 \(n * m\) 的棋盘。左上角的格子为 \((1,1)\)，右下角的格子为 \((n,m)\)。整个棋盘上的格子都有不同的事件，因为生活的多姿多彩，事件的权值\(A_{(i, j)}\)都两两不同。
不幸的是，在整个人生中有若干个极其黑暗的事件，它们的权值 \(A_{(i, j)} = 0\)。更进一步说，对于 \(A_{(i, j)} > 0\) 的事件，权值两两不同。 \(Zyh\) 站在人生的起点 \((1,1)\)，他想要走向人生的巅峰 \((n,m)\)。
\(Zyh\) 认为人只能前进，即若 \(Zyh\) 站在 \((a,b)\)，他只能走向 \((a,b+1)\) 或者 \((a+1,b)\)。
并且 \(Zyh\) 认为黑暗的事件是绝对不可以触碰的，因为一旦经历就会坠入万丈深渊。
\(Zyh\) 会将自己所经历的事件的权值依次写出，形成一个 \(n+m-1\) 的序列。
\(Zyh\) 想知道其中字典序最小的序列是什么。
若是人生过于艰难，没有一个合法序列，就输出 Oh,the life is too difficult!
总结：给定一个n*m的矩阵，矩阵中每个点有一个权值。要求所有从1走到n且不经过权值为0的点的字典序最小的路径序列。
2.样例解释
我们先画一组样例：
3 3
1 3 4
7 9 0
5 6 8
1 3 9 6 8
在图中我们不难发现：矩阵中九个元素，\(4\) 和 \(0\) 是肯定走不了的。
于是我们在剩下七个点中从 \(1\) 出发，在向下和向右两种策略中选择字典序更小的向右 （权值为 \(3\)）。
然后我们发现在 \(3\) 这个点只能向下走，于是我们走到权值为 \(6\) 的点，最后发现不能向下走，所以向右走到终点。
3.思路
结合样例，我们不难得出以下思路：
-
1.从 \((n, m)\) 开始跑一遍 \(bfs\)，标记好一定不能走的点。
-
2.判断 \(vis[1][1]\) 是否为逻辑假，如果是，说明无解。
-
3.从 \((1, 1)\) 开始枚举每个点，如果有两种策略，就选择权值较小的点走，直到走到 \((n, m)\) 为止。
4.注意事项
-
1.由于题中顺着走是向下和向右走，所以倒着跑 \(bfs\) 时就要变为向上和向左走；
-
2.由于代码实现时有差距，最后可能要再输出一遍 \(a_{(n,m)}\) 的值，不要漏掉了！！！
5.代码实现
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
#define N 1010
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(),cin.tie(),cout.tie()
int a[N][N], n, m, vis[N][N];
int dx[2] = {0, -1}, dy[2] = {-1, 0}; //存行动方式的数组
struct no {
int x, y;
};queue <no> q;
void bfs (int x, int y) {
q.push({x, y});
vis[x][y] = 1; //将(n,m)打上逻辑真
while (!q.empty ()) {
no res = q.front ();//取出队头元素
q.pop ();
for (int i = 0; i <= 1; i ++) {
int t1 = res.x + dx[i], t2 = res.y + dy[i]; //模拟下一步
if (t1 >= 1 && t1 <= n && t2 >= 1 && t2 <= m && vis[t1][t2] == 0 && a[t1][t2] != 0) {
//如果下一步还在矩阵范围内，且是还没被用过的非0的点，则走到 (t1,t2) 这个点
q.push ({t1, t2});
vis[t1][t2] = 1;
}
}
}
if (vis[1][1] == 0) { //如果 (1, 1) 是逻辑假，即从 (n, m) 走不到 (1, 1) 这个点
cout << "Oh,the life is too difficult!" << endl;
exit (0); //输出并结束程序。
}
}
signed main () {
cin >> n >> m;
For (i, 1, n) {
For (j, 1, m) {
cin >> a[i][j];
}
}
bfs (n, m);
int x = 1, y = 1;
while (x != n || y != m) {
cout << a[x][y] << " "; //从（1, 1）开始输出
if (vis[x][y + 1] == 0 || y >= m) { //如果不能向下走，就向右走
x ++;
} else if (vis[x + 1][y] == 0 || x >= n) { //如果不能向右走，就向下走
y ++;
} else { //如果都可以，取权值较小的走
if (a[x][y + 1] >= a[x + 1][y]) x ++;
else y ++;
}
}
cout << a[n][m] << endl; //别忘了输出终点
return 0;
}