1 solutions
-
0
注意:本题时间限制 4s,洛谷原题 3s。
难度: 绿
算法标签: 搜索(剪枝),广度优先搜索。
搜索。
应该是广度优先搜索,因为深度优先搜索
具有局限性只能看一个方向。首先预处理出按一个键后跳转到的位置(上下左右都要),此部分你可以写 的,或 的,都没问题。
搜索时记四个状态 ,表示位于第 行, 列,打完 个字符,最小代价 。然后记 为现在在第 行, 列,已经打完了 个字符的最小代价,每次搜到之后如果当前代价不低于原来数组里存的就剪掉,否则更新然后继续搜。形式化的说,如果 就直接剪掉,否则将 赋值 。
别忘了在你的字符串后面加一个
*
。代码(有点长):
#include<bits/stdc++.h> using namespace std; int n,r,c,m,f[52][52][10010],d[52][52],ne[52][52][5],nx,ny,nt,ns,ans; string st; map<char,int> mp; queue<int> x,y,t,s; int main(){ memset(f,0x3f3f3f,sizeof(f)); ans=f[0][0][0]; for(int i='0';i<='9';i++) mp[char(i)]=++m; for(int i='A';i<='Z';i++) mp[char(i)]=++m; mp['-']=++m,mp['*']=++m; scanf("%d%d",&r,&c); for(int i=1;i<=r;i++){ cin>>st; for(int j=1;j<=c;j++) d[i][j]=st[j-1]; } for(int i=1;i<=r;i++){ for(int j=1;j<=c;j++){ for(int k=j+1;k<=c;k++){ if(d[i][j]!=d[i][k]){ ne[i][j][1]=k; break; } } for(int k=j-1;k>=1;k--){ if(d[i][j]!=d[i][k]){ ne[i][j][2]=k; break; } } } } for(int i=1;i<=c;i++){ for(int j=1;j<=r;j++){ for(int k=j+1;k<=r;k++){ if(d[j][i]!=d[k][i]){ ne[j][i][3]=k; break; } } for(int k=j-1;k>=1;k--){ if(d[j][i]!=d[k][i]){ ne[j][i][4]=k; break; } } } } cin>>st; st=st+"*"; f[1][1][0]=1; x.push(1),y.push(1),t.push(0),s.push(0); while(!x.empty()){ nx=x.front(),ny=y.front(),nt=t.front(),ns=s.front(); x.pop(),y.pop(),t.pop(),s.pop(); if(nx<1||ny<1||nx>r||ny>c) continue; if(ns>=ans) continue; if(nt==int(st.length())){ ans=ns; continue; } if(f[nx][ny][nt]<=ns) continue; f[nx][ny][nt]=ns; if(st[nt]==d[nx][ny]){ x.push(nx),y.push(ny),t.push(nt+1),s.push(ns+1); continue; } x.push(ne[nx][ny][3]),y.push(ny),t.push(nt),s.push(ns+1); x.push(ne[nx][ny][4]),y.push(ny),t.push(nt),s.push(ns+1); x.push(nx),y.push(ne[nx][ny][1]),t.push(nt),s.push(ns+1); x.push(nx),y.push(ne[nx][ny][2]),t.push(nt),s.push(ns+1); } printf("%d",ans); return 0; }
- 1
Information
- ID
- 32
- Time
- 4000ms
- Memory
- 1024MiB
- Difficulty
- 9
- Tags
- # Submissions
- 16
- Accepted
- 2
- Uploaded By