每日一题 day69 打卡
Analysis
这道题题目有点难懂，但看懂了之后感觉并不难。
大体思路是先预处理出键盘中每一位的上下左右第一个能到的点的坐标，然后就可以广搜了。
然而，这道题有很多坑点：
1.最后结尾还要加一个' * '
2.还需要加一个剪枝，不然过不了
剪枝：开一个book数组记录在键盘上到每个点所能完成的最终串的长度。如果再次到了一个点发现能完成的还不如之前多就不再走了
3.上面剪枝用的book数组初值要赋成负数（0为什么不行自己好好想想）
处理完这些细节这道题基本就完成了，还有什么不懂的看代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define int long long 7 #define maxn 50+10 8 #define maxm 10000+10 9 #define rep(i,s,e) for(register int i=s;i<=e;++i) 10 #define dwn(i,s,e) for(register int i=s;i>=e;--i) 11 using namespace std; 12 inline int read() 13 { 14 int x=0,f=1; 15 char c=getchar(); 16 while(c<'0'||c>'9') {if(c=='-') x=-x; c=getchar();} 17 while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} 18 return f*x; 19 } 20 inline void write(int x) 21 { 22 if(x<0){putchar('-');x=-x;} 23 if(x>9)write(x/10); 24 putchar(x%10+'0'); 25 } 26 int n,m,len; 27 char map[maxn][maxn]; 28 char target[maxm]; 29 int book[maxn][maxn]; 30 int dx[5]={0,1,0,-1,0},dy[5]={0,0,-1,0,1}; 31 struct node_point 32 { 33 int x,y; 34 }nex[maxn][maxn][5]; 35 struct node_queue 36 { 37 int x,y,l,s; 38 }x[maxm]; 39 queue<node_queue> q; 40 void init() 41 { 42 rep(i,1,n) 43 { 44 rep(j,1,m) 45 { 46 char ch=map[i][j]; 47 rep(k,i+1,n) 48 { 49 if(ch!=map[k][j]) 50 { 51 nex[i][j][1].x=k; 52 nex[i][j][1].y=j; 53 break; 54 } 55 } 56 rep(k,j+1,m) 57 { 58 if(ch!=map[i][k]) 59 { 60 nex[i][j][2].x=i; 61 nex[i][j][2].y=k; 62 break; 63 } 64 } 65 dwn(k,i-1,1) 66 { 67 if(ch!=map[k][j]) 68 { 69 nex[i][j][3].x=k; 70 nex[i][j][3].y=j; 71 break; 72 } 73 } 74 dwn(k,j-1,1) 75 { 76 if(ch!=map[i][k]) 77 { 78 nex[i][j][4].x=i; 79 nex[i][j][4].y=k; 80 break; 81 } 82 } 83 } 84 } 85 } 86 void dfs() 87 { 88 while(!q.empty()) 89 { 90 node_queue now=q.front(); 91 q.pop(); 92 int nx=now.x,ny=now.y,nl=now.l,ns=now.s; 93 if(map[nx][ny]==target[nl+1]) 94 { 95 if(nl+1==len) 96 { 97 write(ns+1); 98 return; 99 } 100 q.push((node_queue){nx,ny,nl+1,ns+1}); 101 } 102 rep(i,1,4) 103 { 104 int xx=nex[nx][ny][i].x,yy=nex[nx][ny][i].y,ss=ns+1; 105 if(xx<1||xx>n||yy<1||yy>m||book[xx][yy]>=nl) continue; 106 book[xx][yy]=nl; 107 q.push((node_queue){xx,yy,nl,ss}); 108 } 109 } 110 } 111 signed main() 112 { 113 114 n=read();m=read(); 115 rep(i,1,n) cin>>map[i]+1; 116 cin>>target+1; 117 len=strlen(target+1); 118 target[++len]='*'; 119 init(); 120 q.push((node_queue){1,1,0,0}); 121 memset(book,0xff,sizeof(book)); 122 dfs(); 123 return 0; 124 }
如有失误请各位大佬斧正（反正我不认识斧正是什么意思）