Link to the original title: [CF1202B](https://codeforces.com/contest/1202/problem/B)
Label: BF, dp, shortest path
Main idea: There is an x-y counter, which randomly adds x or y to the existing number and outputs a bit. After many operations, a series of samples are obtained, such as the following:

For 2-4 counter
 1.0 + 4 = 4, output 04;
2.4 + 4 = 8, output 048
 3.8 + 4 = 12, output 0482
 4.2 + 2 = 4, output 04824
 5.4 + 4 = 8, output 048248

Of course, the above is only a possible case of 2-4 counter, because adding 2 and 4 is completely random.
For i-j counter, if (0<=i, j<=9, i, J are all integers), add several numbers to the given array to make it a possible output of i-j counter, and seek the minimum value of the supplementary number. (Impossible output-1) The output format is as follows:
(row i, column j, represents i-j counter)

-1 17 7 7 7 -1 2 17 2 7 
17 17 7 5 5 5 2 7 2 7 
7 7 7 4 3 7 1 7 2 5 
7 5 4 7 3 3 2 5 2 3 
7 5 3 3 7 7 1 7 2 7 
-1 5 7 3 7 -1 2 9 2 7 
2 2 1 2 1 2 2 2 0 1 
17 7 7 5 7 9 2 17 2 3 
2 2 2 2 2 2 0 2 2 2 
7 7 5 3 7 7 1 3 2 7

Ideas:
(1) Because the range of numbers is very small, bfs can find the minimum number of steps for each case of i-jcounter, and can directly find the answer:

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
 
struct node
{
	int x, step;
	node(int _x,int _step) : x(_x), step(_step){}
};
 
string s;
int Time[10][10][10][10], vis[10]; //Time[i][j][x][y] denotes the minimum number of times that x becomes y with two numbers I and j, and any number of times will return to the origin. 
 
void bfs(int x,int y,int s) //x-y counter achieves the minimum number of steps required for each number from s 
{
	memset(vis,0,sizeof(vis));
	queue <node> q;
	node now(s,0);
	q.push(now);
	while(!q.empty())
	{
		node t = q.front(); 
		q.pop();
		if(!vis[(t.x+x)%10]) //(t.x+x)%10 represents the remainder of the number currently added, and this if is plus x 
		{
			vis[(t.x+x)%10] = 1;
			Time[x][y][s][(t.x+x)%10]=t.step+1;
			q.push(node{(t.x+x)%10,t.step+1});
		}
		if(!vis[(t.x+y)%10])//This if denotes plus y 
		{
			vis[(t.x+y)%10]=1;
			Time[x][y][s][(t.x+y)%10]=t.step+1;
			q.push(node{(t.x+y)%10,t.step+1});
		}
	}
}
 
int main()
{
	memset(Time,-1,sizeof Time);
	for(int i = 0; i < 10; ++i)
		for(int j = 0; j < 10; ++j) //Existence of symmetry saves time
			for(int k = 0; k < 10; ++k)
				bfs(i,j,k);
	cin>>s;
	int len = s.length();
	for(int i = 0; i < 10; ++i)
	{
		for(int j = 0; j < 10; ++j)
		{
			int ans = 0;
			for(int k = 1; k < len; ++k)
			{
				if(Time[i][j][s[k-1]-'0'][s[k]-'0'] == -1)//If it fails to arrive, the value is -1. 
				{
					ans = -1; break;
				}
				ans += Time[i][j][s[k-1]-'0'][s[k]-'0'];
			}
			if(ans == -1)
				cout<<ans<<(j==9?'\n':' ');//j to 9 changed lines 
			else
				cout<<ans-len+1<<(j==9?'\n':' ');//It's actually the number inserted, but we're asking for the number of changes, so subtract one.
		}
	}
	return 0;
}

(2) Application of the shortest path
Firstly, according to the above method, each x-y counter is processed. Each time x, y is selected to represent the distance between X and y, then the shortest path between 0 and 9 can be processed by Freud algorithm, and the shortest path between two digits can be calculated by traversing the number string again. If it can not be reached, it means that it can not be reached under x-y counter. Output - 1;

Let's just add the Floyd algorithm, which enumerates all the possibilities, so we can know the shortest path between two points.
We go from point i to point j in two ways.

• Go straight from i to j
• First from i to k, then from K to j
  This topic is also to find out the transformation that can be achieved in one step, and then expand the situation that multi-step can be reached with the help of the above ideas.
  The code is as follows:

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
typedef  long long ll;
const int inf=0x3f3f3f3f; 
int dis[10][10];//dis[i][j] records the shortest path from I to j 
char s[maxn];
int n;
int fun(int x,int y)//Find out the minimum steps required for x-y counter 
{
    memset(dis,inf,sizeof(dis));
    for(int i=0;i<10;i++)
	{
        dis[i][(i+x)%10]=dis[i][(i+y)%10]=1;//One-step arrival 
    }
    for(int k=0;k<10;k++)
	{
        for(int i=0;i<10;i++)
		{
            for(int j=0;j<10;j++)
			{
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//A point is decomposed into I - > k - > J. 
            }
        }
    }
    ll ans=0;
    for(int i=0;i<n-1;i++)
	{
        if(dis[s[i]-'0'][s[i+1]-'0']==inf)//If it can't be done 
            return -1;
        ans+=dis[s[i]-'0'][s[i+1]-'0']-1;//Since the number of changes is recorded, subtract 1 
    }
    return ans;
 
}
int main(){
    scanf("%s",s);
    n=strlen(s);
    for(int i=0;i<10;i++)
	{
        for(int j=0;j<10;j++)
		{
            cout<<fun(i,j)<<' ';
        }
        cout<<endl;
    }
 
    return 0;
}