[bfs]hdoj 1195

题意

     问从第一个状态转移到第二个状态需要至少几步

 

思路

    按照题意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;
}