题目描述
Greedy得到了一块棋盘作为生日礼物。棋盘有N行M列，每个格子中都有一个小写英文字母。在他的生日聚会上，每个人都很无聊，所以他们决定用棋盘玩一个简单的游戏。 首先在左上角标有坐标（1，1）的格子放置一个棋子。在每一个回合中，我们必须将芯片向右或向下移动一格，前提是没有移出棋盘。游戏结束时，将棋子移动到标有坐标（N，M）的格子即棋盘的右下角。在游戏中，我们依次记下移动棋子时经过的格子里的字母，从而构造一个单词。游戏的目标是找到能构造出的字典序最小的单词。 那些成功地构造了字典序最小单词的玩家会得到一袋糖果作为奖励。Greedy愿意付出任何代价来赢得糖果，所以他要求你写一个程序，可以找到能构造出的字典序最小的单词。
输入
第一行输入包含整数N和M（1≤N，M≤2000）。表示场地的行数和列数。 接下来N行每行包含一个字符串，每个字符串由M个小写英文字母组成。表示棋盘。
输出
输出一个字符串。表示能构造出的字典序最小的单词。
样例输入
4 5
ponoc
ohoho
hlepo
mirko
样例输出
pohlepko对于50%的数据，每个格子下方和右方的格子中的字母是不同的。
解题思路
很明显，一半的点可以直接做，因为它下方和右方的字母不同，我们直接往字典序小的那一个字母遍历即可，当时便是这样暴力，然后相等就一起dfs
如果有相同的，我们就必须要都两个点都要进行遍历，直到其中一个字符串小于另一个字符串，我们就停止另一个字符串的遍历。
于是我们用flag打上标记，用一些神奇的操作可以完成这个遍历。
但好像可以用BFS来判断一下，因为层层扩散的缘故，我们可以只要当前层最优的那一些解（相同的）继续往下搜，其余的不要了。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int n,m,cnt;
char ans[20005],c[2005][2005];
bool flag [2005][2005];
int main(){
//freopen("pohlepko.in","r",stdin);
//freopen("pohlepko.out","w",stdout);
scanf ("%d%d",&n,&m);
for (int i = 1;i <= n;i ++){
scanf ("
");
for (int j = 1;j <= m;j ++){
scanf ("%c",&c[i][j]);
}
}
ans[++ cnt] = c[1][1];
flag[1][1] = 1;
for (int i = 2;i < n + m;i ++){//枚举走的步数，最多为n - 1步
char p = 'z' + 1;
for (int j = 1;j <= min(n,i - 1);j ++){//枚举行数，然后步数减行数得到了列数
if (i - j <= m && flag[j][i - j]){//当前点已经遍历
flag[j + 1][i - j] = flag[j][i - j + 1] = 1;//先打上标记，等下再处理
if (c[j + 1][i - j] >= 'a' && c[j + 1][i - j] <= 'z')//边界情况
p = min(p,c[j + 1][i - j]);//向下走
if (c[j][i - j + 1] >= 'a' && c[j][i - j + 1] <= 'z')
p = min(p,c[j][i - j + 1]);//向右走
}
}
ans [++ cnt] = p;//储存最小的那一个
for (int j = 1;j <= min(n,i);j++){
if (i - j + 1 <= m && flag[j][i - j + 1] && c[j][i - j + 1] != p)//这里删除标记，如果下，右相等，则暂时不会去标，等之后再形成新的字符串再次去标，+1则是因为已经走了这一步。
flag[j][i - j + 1] = 0;
}
}
for (int i = 1;i <= cnt; i ++)
printf("%c",ans[i]);
}