数据
查看原帖
数据
350533
Summer_wind楼主2022/4/29 15:16

为什么这篇题解

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
using namespace std;
const int N=59;
const int M=10009;
struct node{
	int x;
	int y;
	int step;//指下一个到了第几个位置, 
	int dis;//按了几次 
}f[5][N][N];//后两个表示坐标,前一个表示方向,即i,j在k方向上到的最近的点 
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
char wor[M];
int n,m,len,a[N][N],b[M],vis[N][N];
map<char,int> mp;
void prepare()//预先将所有的字符串处理成数字类型的,方便处理
{
	for(int i=0;i<=9;i++)
	mp[(char)('0'+i)]=i+1;
	for(int i=0;i<26;i++)
	mp[(char)('A'+i)]=i+11;//1-10被取过了 
	mp['-']=37;
	mp['*']=38; 
} 
void get()//处理一下四个方向可以到达的点 
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int k=0;k<4;k++)
			{
				int x=i;
				int y=j;
				while(a[x][y]==a[x+dx[k]][y+dy[k]])//如果一致的话 
				{
					x+=dx[k];
					y+=dy[k];//一致加到不同为止 
				}
				f[k][i][j]=(node){x,y,0,0};
			}
}
int search()
{
	memset(vis,0,sizeof(vis));
	queue<node> q;
	int ans=0;
	int k=1;
	while(a[1][1]==b[k]&&k<=len) ++k;//在起点选取的情况
	q.push((node){1,1,k,k-1});
	vis[1][1]=k;
	while(!q.empty())
	{
		node cun=q.front();
		q.pop();
		int x=cun.x;
		int y=cun.y;
		int now=cun.step; 
		if(a[x][y]==b[now])//此时相等了
		{
			if(now==len) 
			{
				ans=cun.dis+1;
				break;//如果找完了?直接跳出 
			}
			vis[x][y]=now+1;//更新一下,因为按了一遍键盘 
			q.push((node){x,y,now+1,cun.dis+1});
		} 
		for(int i=0;i<4;i++)
		{
			node chose=f[i][x][y];
			chose.x+=dx[i];
			chose.y+=dy[i];//预处理上在加一次,保证完整
			if(chose.x<1||chose.x>n||chose.y<1||chose.y>m) continue;//越界了
			if(vis[chose.x][chose.y]>=now) continue;//如果选择的地方的要处理的位置比现在的要大,不用改,防止变worse 
			vis[chose.x][chose.y]=now;//如果可行,那么把接下来要弄得位置给存进去
			q.push((node){chose.x,chose.y,now,cun.dis+1});//跳到那一步 
		} 
	} 
	return ans;
}
int main()
{
	prepare();
	while(scanf("%d",&n)!=EOF)//UVA经典输入方式
	{	
//		cin>>n;
		cin>>m;
		for(int i=1;i<=n;i++)//输入每一行的字符串
		{
			cin>>wor;		
			for(int j=0;j<m;j++)
				a[i][j+1]=mp[wor[j]];//将每个字符的代表的数字映射到a数组中
				//从1开始方便 
		} 
		cin>>wor;
		len=strlen(wor);
		for(int i=0;i<len;i++) b[i+1]=mp[wor[i]];//依旧是映射,从1开始
		len++;
		b[len]=38;//注意最后有一个*
		get();
		cout<<search()<<endl; 
	} 
	return 0;
} 

的这种数据过不了

3 10
qwertyuiop
asdfghjkl-
zxcvbnm--*
azq

是有什么bug吗

2022/4/29 15:16
加载中...