CodeChef Chef and Digit Jumps 题解

原题链接：Chef and Digit Jumps
题意：原题中有链接。
题解：一道很明显的bfs题，就是跳就可以了，当然，跳的时候可以加一些优化，具体看代码

#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
#define Maxn 100000
char s[Maxn+5];
int n;
int a[Maxn+5];
queue<int> q;
vector<int> x[10];
bool in[Maxn+5];
bool vis[10];
void bfs(){
	q.push(1);
	a[1]=0;
	in[1]=1;
	int now;
	while(!q.empty()){
		now=q.front();
		if(now==n){
			break;
		}
		in[now]=0;
		q.pop();
		if(now-1>0&&a[now-1]>a[now]+1){
			a[now-1]=a[now]+1;
			if(!in[now-1]){
				q.push(now-1);
				in[now-1]=1;
			}
		}
		if(now+1<=n&&a[now+1]>a[now]+1){
			a[now+1]=a[now]+1;
			if(!in[now+1]){
				q.push(now+1);
				in[now+1]=1;
			}
		}
		if(vis[s[now]-'0']){
			continue;
		}//每一个数只要跳一次即可，后面来的肯定不会更优
		vis[s[now]-'0']=1;
		for(int i=0;i<(int)x[s[now]-'0'].size();i++){
			if(a[x[s[now]-'0'][i]]>a[now]+1){
				a[x[s[now]-'0'][i]]=a[now]+1;
				if(!in[x[s[now]-'0'][i]]){
					q.push(x[s[now]-'0'][i]);
					in[x[s[now]-'0'][i]]=1;
				}
			}
		}
	}
}
int main(){
	memset(a,0x3f,sizeof a);
	scanf("%s",s+1);
	while(s[++n]!=' '){
		x[s[n]-'0'].push_back(n);
	}
	n--;
	bfs();
	printf("%d
",a[n]);
	return 0;
}