HDU 4433 locker(SPFA+DP)

제목 링크
작년 지역 경기의 제목은 이미 제목을 보았고, 또 한참이 지났다...
이 문제는 상태가 바뀌어서 한 번 보면 선형적인 것이어야 한다는 것을 알 수 있다. 그러나 세부 사항은 정말 처리하기 어려워서 어떻게 해야 할지 생각해 내지 못했다. 그 동안 문제풀이도 봤는데 잘 이해하지 못한 것 같다...
pp[i][j]는 앞의 i위가 같고 i 뒤의 두 자리는 j의 최소 회전 횟수를 나타낸다.
예를 들어 dp[i][x*10+y] i+3위는 z(초기 숫자), xyz는 ax ay az로 전환되고ax는 두 번째 열의 i위가 틀림없으며 두 번째는 마음대로 할 수 있다.
xyz가axayaz로 전환되는 상황을 미리 처리하면 됩니다.dp[0] 초기화, 100자리 직접 플로이드, 기타 1000자리 예처리, spfa로 만들었습니다.
예처리가 길다.

  1 #include <cstring>

  2 #include <cstdio>

  3 #include <string>

  4 #include <iostream>

  5 #include <algorithm>

  6 #include <vector>

  7 #include <queue>

  8 using namespace std;

  9 #define INF 10000000

 10 char s1[1200],s2[1200];

 11 int dp[1010][110];

 12 int mp[1010][1010];

 13 int dis[1010];

 14 int in[1010];

 15 int p[101][101];

 16 int n1[1010],n2[1010];

 17 int a[12] = {1,0,0,1,0,1,-1,0,0,-1,0,-1};

 18 int b[12] = {0,1,0,1,1,1,0,-1,0,-1,-1,-1};

 19 int c[12] = {0,0,1,0,1,1,0,0,-1,0,-1,-1};

 20 void spfa(int key)

 21 {

 22     int x,y,z,i,ax,ay,az,u,v;

 23     queue <int> que;

 24     for(i = 0;i < 1000;i ++)

 25     {

 26         dis[i] = INF;

 27         in[i] = 0;

 28     }

 29     in[key] = 1;

 30     dis[key] = 0;

 31     que.push(key);

 32     while(!que.empty())

 33     {

 34         u = que.front();

 35         in[u] = 0;

 36         que.pop();

 37         x = (u/100)%10;

 38         y = (u/10)%10;

 39         z = u%10;

 40         for(i = 0;i < 12;i ++)

 41         {

 42             ax = (x+a[i]+10)%10;

 43             ay = (y+b[i]+10)%10;

 44             az = (z+c[i]+10)%10;

 45             v = ax*100+ay*10+az;

 46             if(dis[v] > dis[u] + 1)

 47             {

 48                 if(!in[v])

 49                 {

 50                     in[v] = 1;

 51                     que.push(v);

 52                 }

 53                 dis[v] = dis[u] + 1;

 54             }

 55         }

 56     }

 57     for(i = 0;i < 1000;i ++)

 58     mp[key][i] = dis[i];

 59     return ;

 60 }

 61 int main()

 62 {

 63     int i,j,len,x,y,z,k,temp;

 64     for(i = 0;i < 100;i ++)

 65     {

 66         for(j = 0;j < 100;j ++)

 67         p[i][j] = INF;

 68         p[i][i] = 0;

 69     }

 70     for(i = 0;i < 100;i ++)

 71     {

 72         x = (i/10)%10;

 73         y = i%10;

 74         p[x][(y+1)%10] = 1;

 75         p[(y+1)%10][x] = 1;

 76         p[(x+1)%10][y] = 1;

 77         p[y][(x+1)%10] = 1;

 78         p[(x+1)%10][(y+1)%10] = 1;

 79         p[(y+1)%10][(x+1)%10] = 1;

 80     }

 81     for(i = 0;i < 100;i ++)

 82     {

 83         for(j = 0;j < 100;j ++)

 84         {

 85             for(k = 0;k < 100;k ++)

 86             {

 87                 if(p[j][k] > p[j][i] + p[i][k])

 88                 p[j][k] = p[j][i] + p[i][k];

 89             }

 90         }

 91     }

 92     for(i = 0;i < 1000;i ++)

 93     {

 94         spfa(i);

 95     }

 96     while(scanf("%s%s",s1,s2)!=EOF)

 97     {

 98         len = strlen(s1);

 99         for(i = 1;i <= len;i ++)

100         {

101             n1[i] = s1[i-1] - '0';

102             n2[i] = s2[i-1] - '0';

103         }

104         for(i = 0;i <= len;i ++)

105         {

106             for(j = 0;j < 100;j ++)

107             dp[i][j] = INF;

108         }

109         n1[len+1] = n2[len+1] = 0;

110         n1[len+2] = n2[len+2] = 0;

111         temp = n1[1] * 10 + n1[2];

112         for(i = 0;i < 100;i ++)

113         {

114             dp[0][i] = p[temp][i];

115         }

116         for(i = 0;i < len;i ++)

117         {

118             z = n1[i+3];

119             for(j = 0;j < 100;j ++)

120             {

121                 x = (j/10)%10;

122                 y = j%10;

123                 for(k = 0;k < 100;k ++)

124                 {

125                     if(dp[i+1][k] > dp[i][j] + mp[j*10+z][n2[i+1]*100+k])

126                     dp[i+1][k] = dp[i][j] + mp[j*10+z][n2[i+1]*100+k];

127                 }

128             }

129         }

130         printf("%d
",dp[len][0]);

131     }

132     return 0;

133 }