题意
? ? ?问从第一个状态转移到第二个状态需要至少几步
?
思路
? ? 按照题意bfs一遍即可
?
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; class sta{ public: char str[5]; int step; }; queue<sta>que; int vis[11][11][11][11]; bool getvis(sta a){ if(!vis[a.str[0]-‘0‘][a.str[1]-‘0‘][a.str[2]-‘0‘][a.str[3]-‘0‘]){ vis[a.str[0]-‘0‘][a.str[1]-‘0‘][a.str[2]-‘0‘][a.str[3]-‘0‘] = 1; return 1; } return 0; } int main(){ int tcas,i; scanf("%d",&tcas); sta a, q; char ed[10]; while(tcas--){ scanf("%s%s",a.str,ed); // vis.clear(); memset(vis, 0, sizeof(vis)); while(!que.empty())que.pop(); a.step = 0; que.push(a); vis[a.str[0]-‘0‘][a.str[1]-‘0‘][a.str[2]-‘0‘][a.str[3]-‘0‘] = 1; while(!que.empty()){ q = que.front(); que.pop(); // cout<<q.str<<endl; if(strcmp(q.str,ed) == 0){ printf("%d\n",q.step); break; } a.step = q.step + 1; for(i = 0; i < 4; i++){ strcpy(a.str,q.str); a.str[i]++; if(a.str[i] == ‘9‘ + 1)a.str[i] = ‘1‘; if(getvis(a))que.push(a); a.str[i] = q.str[i]; a.str[i] -- ; if(a.str[i] == ‘1‘ - 1)a.str[i] = ‘9‘; if(getvis(a))que.push(a); if(i <= 2){ strcpy(a.str,q.str); char tmp; tmp = a.str[i]; a.str[i] = a.str[i+1]; a.str[i+1] = tmp; if(getvis(a))que.push(a); } } } } return 0; }
?
原文:http://bbezxcy.iteye.com/blog/2165696