Keyboarding（信息学奥赛一本通-T1452）

【题目描述】
出自 World Final 2015 F. Keyboarding

给定一个 r 行 c 列的在电视上的“虚拟键盘”，通过「上，下，左，右，选择」共 5 个控制键，你可以移动电视屏幕上的光标来打印文本。一开始，光标在键盘的左上角，每次按方向键，光标总是跳到下一个在该方向上与当前位置不同的字符，若不存在则不移动。每次按选择键，则将光标所在位置的字符打印出来。

现在求打印给定文本（要在结尾打印换行符）的最少按键次数。

【输入】
第一行输入 r,c。

接下来给出一个 r×c 的键盘，包括大写字母，数字，横线以及星号（星号代表 Enter 换行）。

最后一行是要打印的文本串 S，S 的长度不超过 10000。

【输出】
输出打印文本（包括结尾换行符）的最少按键次数。保证一定有解。

【输入样例】
2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ
【输出样例】
19
【提示】
样例输入2:

5 20
12233445566778899000
QQWWEERRTTYYUUIIOOPP
-AASSDDFFGGHHJJKKLL*
--ZZXXCCVVBBNNMM--**

ACM-ICPC-WORLD-FINALS-2015
样例输出2:

160
样例输入3:

6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB
样例输出 3

7
数据范围：

对于 100% 的数据，1≤r,c≤50, S 的长度不超过 10000。

用 vis 记录访问时打印字符串的个数，如果当前节点打印个数小于 vis 就无需向下拓展
双端队列优化，对于能直接打印字符的节点插入到队头，不能直接打印字符的节点插入到队尾

#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>
#include <iostream>
#pragma GCC optimize(1)


using namespace std;

const int N = 10000 + 10;

char f[60][60];
int r, c;
char s[N];
int l;

int vis[60][60];
int ds[55][55][4][3];

struct node
{
	int x, y, d;
	int step;
};
int dx[4] = {0 , 0, 1, -1};
int dy[4] = {1, -1, 0 , 0};
int ans  = 0x7ffffff;

void print(int x)
{
	for(int i = 0 ;i < x; i++) printf("%c",s[i]);
	printf("   ");
}

void pre()//预处理
{
	for(int i = 1; i <= r; i++)
	{
		for(int j = 1; j <= c; j++)
		{
			for(int k = 0; k < 4; k++)
			{
				int x = i, y = j;
				while(f[x][y] == f[i][j])
				{
					x += dx[k];
					y += dy[k];
					if(x < 0 || y < 0)
					{
						break;
					}
					if(!(x > 0 && x <= r && y >0 && y <= c)) break;
				}
				if(x > 0 && x <= r && y >0 && y <= c)
				{
					ds[i][j][k][0] = x;
					ds[i][j][k][1] = y;
				}
			}
		}
	}
}

void bfs()
{
	deque <node> q;
	q.push_back((node){
		1,1,0,0
	});
	while(q.size())
	{
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		int step = q.front().step;
		q.pop_front();
	//	cout << x <<" "<<y <<" "<<d<<" "<<step<<"n";
	//	print(d);
	//	printf("%c    %cn",f[x][y],s[d]);
		
		if(s[d] == f[x][y]) //在一个位置重复按
		{
			int cnt = 0;
			int  p = d;
			while(f[x][y] == s[p])
			{
				cnt++;
				p++;
			}
			d += cnt;
			step += cnt;
			q.push_front((node){// 插入到队头
				x,y,d ,step
			});
		}
		if(d == l + 1)
		{
			printf("%d",step);
			return ;
		}
		for(register int i = 0; i < 4; i++)
		{
			int xx = ds[x][y][i][0];
			int yy = ds[x][y][i][1];
			//cout<<xx<<" "<<yy<<"n";
			if(xx > 0 && xx <= r && yy > 0 && yy <= c && vis[xx][yy] < d)
			{
				vis[xx][yy] = d;
				q.push_back((node){
					xx,yy,d,step + 1
				});//插入到队尾
			}
		}
	}
} 

int main()
{
	scanf("%d %d",&r,&c);
	getchar();
	for(register int i = 1; i <= r; i++)
	{
		for(register int j = 1; j <= c; j++)
		{
			f[i][j] = getchar();
		}
		getchar();
	}
	scanf("%s",s);
	pre();
	l = strlen(s);
	s[l] = '*';
	memset(vis,-1,sizeof(vis));
	bfs();
	return 0;
}

• 还没有人评论，欢迎说说您的想法！

相关课程

基于 OpenVINO™ 的 AI 视觉应用进阶课

42053 0元 限免

英特尔 OpenCV 初级认证课程

7736 0元 限免

英特尔® OpenVINO™工具套件初级课程

293090 0元 限免