子序列问题

BFS

首先我们忽略起始数字，因为我们实际上可以把所有的起始数字转化为0000和密码转动起始数字 所以题目只有10000种输入（0000~9999）

考虑打表，开长度10000的表，由0000递推，每次转动一位，记录所需要转动到的最短的次数，总共有10种转动方法，求最短所以使用BFS

最后用一些方法处理四位输入，然后直接队列bfs，过

#include <stdio.h>
#include <stdlib.h>
#include <iostream> 
#include <cstring>
#include <queue>
using namespace std; 

int hax[10010];
int gnum[10][4]={
	{0,0,0,1},
	{0,0,1,0},
	{0,1,0,0},
	{1,0,0,0},
	{0,0,1,1},
	{0,1,1,0},
	{1,1,0,0},
	{0,1,1,1},
	{1,1,1,0},
	{1,1,1,1}
};
int tnum[2]={1,-1};
int main()
{
	int t;
	scanf("%d",&t);
	memset(hax,0x3f3f3f3f,sizeof hax);
	
	hax[0]=0;
	queue<int> que;
	que.push(0);
	while(!que.empty()){
		int now=que.front();
		int tnow=now;
		que.pop();
		int num[4];
		for(int i=0;i<4;++i){
			num[i]=tnow%10;
			tnow/=10;
		}
		int nnum[4];
		for(int g=0;g<2;++g)
		for(int i=0;i<10;++i){
			int sum=0,tsum=1;
			for(int r=0;r<4;++r){
				nnum[r]=num[r]+tnum[g]*gnum[i][r]+10;
				nnum[r]%=10;
				sum+=tsum*nnum[r];
				tsum*=10;
			}
			if(hax[sum]>hax[now]+1){
				hax[sum]=hax[now]+1;
				que.push(sum);
			}
		}
	} 
	while(t--){
		int s,e;
		scanf("%d%d",&s,&e);
		int sum=0;
		for(int i=0;i<4;++i){
			sum*=10;
			sum+=(e%10-s%10+10)%10;
			e/=10;
			s/=10;
		}
		printf("%d\n",hax[sum]);
	}
	return 0;
}