[第三场T2]Pohlepko 考试

【[第三场T2]Pohlepko】
题目描述
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 #include #include #include #include #include #include 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 ("\n"); 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]); }