HDU1195Open the Lock(AC)_twinslizzy’s blog

class=”htmledit_views”>

Open the Lock
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5480 Accepted Submission(s): 2442

Problem Description

Now an emergent task for you is to open a password lock. The password is consisted of four digits. Each digit is numbered from 1 to 9.
Each time, you can add or minus 1 to any digit. add 1 to ‘9’, the digit will change to be ‘1’ and when minus 1 to ‘1’, the digit will change to be ‘9’. You can also exchange the digit with its neighbor. Each action will take one step.

Now your task is to use minimal steps to open the lock.

Note: The leftmost digit is not the neighbor of the rightmost digit.

Input

The input file begins with an integer T, indicating the number of test cases.

Each test case begins with a four digit N, indicating the initial state of the password lock. Then followed a line with another four night M, indicating the password which can open the lock. There is one blank line after each test case .

Output

For each test case, print the minimal steps in one line.

Sample Input

2
1234
2144

1111
9999

Sample Output

2
4

#define _CRT_SECURE_NO_WARNINGS

 #include 
 char cinit[4];
 int init[4];
 int right[4];
 char cright[4];
 int ans = 0;
 int cur = 0;
 int front = 0;

 #define MAXINT 1000000

 int visit[11][11][11][11]; //0--original data, 1--addition, 2--subtraction, 3--adjacent exchange, this visit was just wrongly written int visit[5]  [4] It’s useless, I saw int visit[11][11][11][11] on the Internet, BFS still needs a mark

 /*This person's approach and my approach are like http://bbs.csdn.net/topics/340202380*/


 //The first time I submitted WA, why is 1234->2144 2 instead of 3? Well, this question also has the idea of ​​​​adjacent exchange.  .
 //The second submission is still WA, continue to check for errors
 //The third submission of runtime timed out, well, bfs will also time out, and I am also drunk.  .  .  .  But the code written by myself is indeed more troublesome, not concise
 //Simplify the code, use an array, but it still times out, hey hey hey, isn't this question very simple?  .  .  .  .
 //20160126 submission becomes WA again, I am also drunk
 //The 20160126BFS() exchange code is a bit problematic, OK HDUAC, 453ms, the time is not fast

 typedef struct node
 {
 int step;
 int xxx[5];
 }nodes;

 nodes que[MAXINT];

 void BFS()
 {
 int i = 0;
 int j = 0;
 int quex[5] = { 0 };
 int tmpx[5] = { 0 };
 int queststep = 0;

 que[cur].xxx[1] = init[0];
 que[cur].xxx[2] = init[1];
 que[cur].xxx[3] = init[2];
 que[cur].xxx[4] = init[3];
 que[cur++].step = 0;

 visit[init[0]][init[1]][init[2]][init[3]] = 1;

 while (front<cur)
 {
 tmpx[1] = que[front].xxx[1];
 tmpx[2] = que[front].xxx[2];
 tmpx[3] = que[front].xxx[3];
 tmpx[4] = que[front].xxx[4];
 questep = que[front].step;
 if ((tmpx[1] == right[0]) && (tmpx[2] == right[1]) && (tmpx[3] == right[2]) && (tmpx[4] == right[  3]))
 {
 ans = queststep;
 return;
 }
 //Refers to start from i bit+
 for (i = 1; i <= 4; i++)
 {

 quex[1] = tmpx[1];
 quex[2] = tmpx[2];
 quex[3] = tmpx[3];
 quex[4] = tmpx[4];
 if (tmpx[i] == 9)
 {
 quex[i] = 1;
 }
 else
 {
 quex[i] = tmpx[i] + 1;
 }

 if (1 == visit[quex[1]][quex[2]][quex[3]][quex[4]]) continue;
 que[cur].xxx[1] = quex[1];
 que[cur].xxx[2] = quex[2];
 que[cur].xxx[3] = quex[3];
 que[cur].xxx[4] = quex[4];
 que[cur++].step = questep + 1;
 visit[quex[1]][quex[2]][quex[3]][quex[4]] = 1;
 }

 // means starting from the i position -
 for (i = 1; i <= 4; i++) //
 {
 quex[1] = tmpx[1];
 quex[2] = tmpx[2];
 quex[3] = tmpx[3];
 quex[4] = tmpx[4];
 if (tmpx[i] == 1)
 {
 quex[i] = 9;
 }
 else
 {
 quex[i] = tmpx[i] - 1;
 }
 if (1 == visit[quex[1]][quex[2]][quex[3]][quex[4]]) continue;
 que[cur].xxx[1] = quex[1];
 que[cur].xxx[2] = quex[2];
 que[cur].xxx[3] = quex[3];
 que[cur].xxx[4] = quex[4];
 que[cur++].step = questep + 1;
 visit[quex[1]][quex[2]][quex[3]][quex[4]] = 1;
 }

 		//exchange
 for (i = 1; i <= 3; i++) //
 {
 quex[1] = tmpx[1];
 quex[2] = tmpx[2];
 quex[3] = tmpx[3];
 quex[4] = tmpx[4];

 quex[i] = tmpx[i + 1];
 quex[i + 1] = tmpx[i];
 if (1 == visit[quex[1]][quex[2]][quex[3]][quex[4]]) continue;

 que[cur].xxx[1] = quex[1];
 que[cur].xxx[2] = quex[2];
 que[cur].xxx[3] = quex[3];
 que[cur].xxx[4] = quex[4];
 que[cur++].step = questep + 1;
 visit[quex[1]][quex[2]][quex[3]][quex[4]] = 1;
 }
 		
 front++;
 }
 return;
 }

 void inits()
 {
 int i = 0;
 int j = 0;
 int k = 0;
 int m = 0;
 for (i = 0; i < MAXINT; i++)
 {
 que[i].step = 0;
 for (j = 0; j < 5; j++)
 {
 que[i].xxx[j] = 0;
 }
 }

 for (i = 0; i < 11; i++)
 {
 for (j= 0; j < 11; j++)
 {
 for (k = 0; k < 11; k++)
 {
 for (m = 0; m < 11; m++)
 {
 visit[i][j][k][m] = 0;
 }
 }
 }
 }

 cur = 0;
 front = 0;
 return;
 }

 int main()
 {
 int T = 0;
 int i = 0;
 int j = 0;
 freopen("input.txt", "r", stdin);
 scanf("%d",&T);
 for (i = 0; i < T; i++)
 {
 ans = 0;
 inits();
 scanf("%s%s", &cinit, &cright);
 for (j = 0; j < 4; j++)
 {
 init[j] = cinit[j] - '0';
 right[j] = right[j] - '0';
 }

 BFS();

 printf("%d\n",ans);
 }
 return 0;
 }