【广搜】Keyboarding

题目描述

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

 

输入

第一行输入 r,c。
接下来给出一个 r×c的键盘，包括大写字母，数字，横线以及星号（星号代表 Enter 换行）。
最后一行是要打印的文本串 S，S 的长度不超过 10000。

 

输出

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

 

样例输入

2 19 ABCDEFGHIJKLMNOPQZY X*****************Y AZAZ

样例输出

19

 

提示

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

 

---

---

 

【题解】

这个题目需要大家耐心处理细节，预处理所有点的四个方向能到达的地方。

然后用BFS搜索，注意搜索的顺序，已经利用好vis标记数组来记录。

 这个题目是真的需要小心，很多坑。

需要设定一个结构体，这个结构体需要提供记录  当前的坐标（x，y），匹配到下标 step，当前结点的花费的操作次数 dis

1、预处理所有位置的四个方向的下一个位置是什么？

2、设置标准的BFS框架，其中入队列之前，可以预处理左上角就是目标串的字符。

3、进入BFS框架时需要两部分，一个是选择，另一个是四个方向遍历，充分要利用vis数组来更新最优值

 

1 #pragma GCC optimize("Ofast") //编译环境优化 2 #include<bits/stdc++.h> 3 using namespace std; 4 const int N = 52 ; 5 const int M = 1e5+10; 6 const int P = 300; 7 char s[M]; 8 int n,m,len; 9 int Map[P],vis[N][N]; 10 int a[N][N],b[M]; 11 typedef struct Node{ 12 int x,y,step,dis; 13 }Node ; 14 Node F[N][N][4]; 15 16 int dir[4][2]={ 17 {-1,0}, 18 {0,-1},{0,1}, 19 {1,0} 20 }; 21 void read_Char(char s[]){ 22 int len = 0 ; 23 char c = getchar() ; 24 while ( c!='\n' ){ 25 s[len++] = c; 26 c = getchar(); 27 } 28 s[len] = '\0'; 29 } 30 void _Map(){ 31 for(int i=0;i<=9;i++){ 32 Map[char('0'+i)] = i+1; 33 } 34 for (int i=0;i<26;i++){ 35 Map[char('A'+i)] = i+11; 36 } 37 Map['-'] = 37 ; 38 Map['*'] = 38 ; 39 } 40 //预处理，处理每一个方向能到达的位置 41 void Init(){ 42 for(register int i=1;i<=n;i++){ 43 for(register int j=1;j<=m;j++){ 44 for(register int k=0;k<4;k++){ 45 int tx = i,ty = j ; 46 while( a[i][j] == a[tx+dir[k][0]][ty+dir[k][1]] ) 47 tx += dir[k][0] , ty += dir[k][1]; 48 F[i][j][k] = (Node) {tx,ty,0,0}; 49 } 50 } 51 } 52 } 53 int BFS(){ 54 55 memset(vis,0,sizeof(vis)); 56 int k = 1 ; 57 //处理左上角就是目标的输出 58 while ( a[1][1] == b[k] && k<=len ) k++ ; 59 queue <Node> Q; 60 Q.push( (Node){1,1,k,k-1} ) ; 61 vis[1][1] = k ; 62 while( !Q.empty() ){ 63 64 Node cur = Q.front(); 65 //printf("(%d,%d)\n",cur.x,cur.y); 66 Q.pop(); 67 //如果找到合适的位置则"选择" 68 if( a[cur.x][cur.y] == b[cur.step] ){ 69 if( cur.step == len ){ 70 return cur.dis + 1 ; 71 } 72 vis[cur.x][cur.y] = cur.step + 1 ; 73 Q.push( (Node) { cur.x,cur.y,cur.step+1,cur.dis+1} ) ; 74 continue ; 75 } 76 //四个方向 77 for(int i=0;i<4;i++){ 78 Node Next = F[cur.x][cur.y][i] ; 79 Next.x += dir[i][0]; 80 Next.y += dir[i][1]; 81 82 if( !(1<=Next.x && Next.x<=n && 1<=Next.y && Next.y<=m) ){ 83 continue; 84 } 85 //if( a[cur.x][cur.y] == a[Next.x][Next.y] ) continue; 86 // 如果后面剪枝过的 87 if( vis[Next.x][Next.y] >= cur.step ) continue ; 88 vis[Next.x][Next.y] = cur.step ; 89 Q.push((Node){Next.x,Next.y,cur.step,cur.dis+1} ); 90 } 91 } 92 } 93 int main() 94 { 95 _Map(); 96 //while( cin >> n >> m ){ 97 while(~scanf("%d%d",&n,&m)){ 98 //memset(a,'\0',sizeof(a)); 99 for(register int i=1;i<=n;i++){ 100 scanf("%s",s+1); 101 //cin >> s+1 ; 102 for(register int j=1;j<=m;j++){ 103 a[i][j] = Map[s[j]]; 104 } 105 } 106 scanf("%s",s+1); 107 //cin >> s+1 ; 108 len = strlen(s+1); 109 for(register int i=1;i<=len;i++){ 110 b[i] = Map[s[i]]; 111 } 112 b[++len] = Map['*']; 113 Init(); 114 printf("%d\n",BFS()); 115 //cout << BFS() << endl; 116 } 117 return 0; 118 } 119 /* 120 2 19 121 ABCDEFGHIJKLMNOPQZY 122 X*****************Y 123 AZAZ 124 */ Keyboarding

 

 

转载于:https://www.cnblogs.com/Osea/p/11215807.html

总结

以上是生活随笔为你收集整理的【广搜】Keyboarding的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。