• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

小S有个n×m的字符矩阵,里面都是小写字母。

现在小S每一步可以向下或者向右走,从左上角走到右下角。现在他想让他走出的字母拼接起来字典序最小。

输入格式
第一行两个整数n,m。

接下来n行,每行长度为m的字符串,表示该矩阵。

输出格式
一个长度为n+m−1的字符串表示答案。

样例1
input

4 5
ponoc
ohoho
hlepo
mirko 

output

pohlepko 

样例2
input

4 5
bbbbb
bbbbb
bbabb
bbbbb

output

bbbbabbb 

数据范围
40%的数据:对于每个位置,它下面的和它右面的字符不同。

100%的数据:\(1≤n,m≤2000\)
时间限制:1S

空间限制:256MB

考虑40%数据点,如果下面的和右面的不同,那就取最小值。

但是相同呢?开一个队列表示现在那些到了的点都相同的位置,然后都往下往右扩展,找到一个最小值。一个点如果等于那个最小值,那就把他放到下一次扩展的队列里。

#include<cstdio>
#include<iostream>
using namespace std;
const int N=2005;
int qx[2][N],qy[2][N],n,m,t,p,idx,k,mn,v[N][N];
char s[N][N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	qx[0][1]=qy[0][idx=p=1]=1;
	putchar(s[1][1]);
	for(idx=1;;idx++)
	{
		k=0,mn=500;
		for(int i=1;i<=p;i++)
		{
			if(qx[t][i]!=n)
				mn=min(mn,(int)s[qx[t][i]+1][qy[t][i]]);
			if(qy[t][i]!=m)
				mn=min(mn,(int)s[qx[t][i]][qy[t][i]+1]);
		}
		for(int i=1;i<=p;i++)
		{
			if(qx[t][i]!=n&&(int)s[qx[t][i]+1][qy[t][i]]==mn&&v[qx[t][i]+1][qy[t][i]]!=idx)
				qx[!t][++k]=qx[t][i]+1,qy[!t][k]=qy[t][i],v[qx[t][i]+1][qy[t][i]]=idx;
			if(qy[t][i]!=m&&(int)s[qx[t][i]][qy[t][i]+1]==mn&&v[qx[t][i]][qy[t][i]+1]!=idx)
				qx[!t][++k]=qx[t][i],qy[!t][k]=qy[t][i]+1,v[qx[t][i]][qy[t][i]+1]=idx;
		}
		if(k)
			p=k,t^=1;
		else
			break;
		putchar(mn);
	}	
}
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now