1 solutions

  • 0
    @ 2023-10-22 21:31:54

    注意:本题时间限制 4s,洛谷原题 3s

    难度: 绿

    算法标签: 搜索(剪枝),广度优先搜索。

    搜索。

    应该是广度优先搜索,因为深度优先搜索具有局限性只能看一个方向。

    首先预处理出按一个键后跳转到的位置(上下左右都要),此部分你可以写 O(n3)O(n^3) 的,或 O(n2)O(n^2) 的,都没问题。

    搜索时记四个状态 i1,j1,k1,si_{1},j_{1},k_{1},s ,表示位于第 i1i_{1} 行,j1j_{1} 列,打完 k1k_{1} 个字符,最小代价 ss 。然后记 f[i][j][k]f[i][j][k] 为现在在第 ii 行,jj 列,已经打完了 kk 个字符的最小代价,每次搜到之后如果当前代价不低于原来数组里存的就剪掉,否则更新然后继续搜。形式化的说,如果 f[i][j][k]sf[i][j][k]\le s 就直接剪掉,否则将 f[i][j][k]f[i][j][k] 赋值 ss

    别忘了在你的字符串后面加一个 *

    代码(有点长):

    #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