问题描述 XXX刚刚拿了NOI金牌,非常开心,于是他举办了一个庆祝活动,让大家一起玩一个棋盘游戏,游戏规则如下:
棋盘可视为N行M列的二维矩阵,每个格子内有一个英文小写字母。
游戏始于棋盘左上角坐标为(1,1)的格子,止于右下角坐标为(N,M)的格子,每一步只能向右或向下移动一格。在游戏的过程中,按顺序记录途径格子上的英文字母,可以构成一个单词。游戏的目标是找到一个字典序最小的单词。
请你帮助XXX找到字典序最小的单词。
输入格式 第一行包含两个用空格隔开的整数N 和 M。
接下来 N行,每行M 个英文小写字母,表示棋盘的每一个格子。
输出格式 一行,输出字典序最小的单词。
样例输入 3 6 xuiotp dwhajv fzqzyc 样例输出 xdfzqzyc 数据范围 对于50%的数据,每个格子右边和下边的两个英文字母不同。
对于100%的数据,1≤N,M≤2000
#include<bits/stdc++.h>
using namespace std;
int main() {
char a[1005][1005];
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=m;i++)
a[n+1][m]=127;//边界
for(int i=1;i<=m;i++)
a[n][m+1]=127;
cout<<a[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(a[i+1][j]<a[i][j+1]){
cout<<a[i+1][j];
i=i+1;j=j;
}
else{
cout<<a[i][j+1];
j++;
}
}
return 0;
}
为什么过不了样例