湖南免费网站建设,德州网站设计,58同城网站建设方案,windows7 iis配置 网站题目描述 给定一个r行c列的在电视上的“虚拟键盘”#xff0c;通过“上#xff0c;下#xff0c;左#xff0c;右#xff0c;选择”共5个控制键#xff0c;你可以移动电视屏幕上的光标来打印文本。一开始#xff0c;光标在键盘的左上角#xff0c;每次按方向键#xf… 题目描述 给定一个r行c列的在电视上的“虚拟键盘”通过“上下左右选择”共5个控制键你可以移动电视屏幕上的光标来打印文本。一开始光标在键盘的左上角每次按方向键光标总是跳到下一个在该方向上与当前位置不同的字符若不存在则不移动。每次按选择键则将光标所在位置的字符打印出来。现在求打印给定文本要在结尾打印换行符的最少按键次数。 输入 第一行输入 r,c。接下来给出一个 r×c的键盘包括大写字母数字横线以及星号星号代表 Enter 换行。最后一行是要打印的文本串 SS 的长度不超过 10000。 输出 输出打印文本包括结尾换行符的最少按键次数。保证一定有解。 样例输入 2 19
ABCDEFGHIJKLMNOPQZY
X*****************Y
AZAZ样例输出 19提示 对于100%的数据1≤r,c≤50,S的长度不超过10000。 【题解】 这个题目需要大家耐心处理细节预处理所有点的四个方向能到达的地方。 然后用BFS搜索注意搜索的顺序已经利用好vis标记数组来记录。 这个题目是真的需要小心很多坑。 需要设定一个结构体这个结构体需要提供记录 当前的坐标xy匹配到下标 step当前结点的花费的操作次数 dis 1、预处理所有位置的四个方向的下一个位置是什么 2、设置标准的BFS框架其中入队列之前可以预处理左上角就是目标串的字符。 3、进入BFS框架时需要两部分一个是选择另一个是四个方向遍历充分要利用vis数组来更新最优值 1 #pragma GCC optimize(Ofast) //编译环境优化2 #includebits/stdc.h3 using namespace std;4 const int N 52 ;5 const int M 1e510;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 i0;i9;i){32 Map[char(0i)] i1;33 }34 for (int i0;i26;i){35 Map[char(Ai)] i11;36 }37 Map[-] 37 ;38 Map[*] 38 ;39 }40 //预处理处理每一个方向能到达的位置41 void Init(){42 for(register int i1;in;i){43 for(register int j1;jm;j){44 for(register int k0;k4;k){45 int tx i,ty j ;46 while( a[i][j] a[txdir[k][0]][tydir[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] klen ) 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.step1,cur.dis1} ) ;74 continue ;75 }76 //四个方向77 for(int i0;i4;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( !(1Next.x Next.xn 1Next.y Next.ym) ){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.dis1} );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 i1;in;i){
100 scanf(%s,s1);
101 //cin s1 ;
102 for(register int j1;jm;j){
103 a[i][j] Map[s[j]];
104 }
105 }
106 scanf(%s,s1);
107 //cin s1 ;
108 len strlen(s1);
109 for(register int i1;ilen;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
