HDU 1195 Open the Lock

1195 Open the Lock 
http://acm.hdu.edu.cn/showproblem.php?pid=1195  
大致題意：給你兩個四位數，一個作為開始一個作為目標，有三種操作每個位可以加1可以減1，可以與相鄰的交換，都算一步，求轉化到目標的最小步數 
#include<iostream>  
#include<queue>  
using namespace std; 
 
char start[5], end[5]; 
int visited[10000]; 
struct node  
{ 
    char str[5]; 
    int step; 
}; 
 
void BFS() 
{ 
    queue<node> Q; 
    node q; 
    strcpy(q.str, start); 
    q.step = 0; 
    Q.push(q); 
    while (!Q.empty()) 
    { 
        q = Q.front(); 
        Q.pop(); 
        if(strcmp(q.str, end) == 0) 
        { 
            cout<<q.step<<endl; 
            return; 
        } 
        //+1  
        for (int i = 0; i<4; i++) 
        { 
            node p = q; 
            if (p.str[i] == '9') p.str[i] = '1'; 
            else p.str[i] += 1; 
            p.step++;//加一步  
            int temp; 
            sscanf(p.str, "%d", &temp); 
            if (!visited[temp]) 
            { 
                visited[temp] = 1;//標記  
                Q.push(p); 
            } 
        } 
        //-1  
        for (i = 0; i<4; i++) 
        { 
            node p = q; 
            if (p.str[i] == '1') p.str[i] = '9'; 
            else p.str[i] -= 1; 
            p.step++;//加一步  
            int temp; 
            sscanf(p.str, "%d", &temp); 
            if (!visited[temp]) 
            { 
                visited[temp] = 1;//標記  
                Q.push(p); 
            } 
        } 
        //exchange  
        for (i = 0; i<3; i++) 
        { 
            node p = q; 
            char t; 
            t = p.str[i]; 
            p.str[i] = p.str[i + 1]; 
            p.str[i + 1] = t; 
            p.step++;//加一步  
            int temp; 
            sscanf(p.str, "%d", &temp); 
            if (!visited[temp]) 
            { 
                visited[temp] = 1;//標記  
                Q.push(p); 
            } 
        } 
    } 
} 
 
int main() 
{ 
    int T;   
    cin>>T; 
    while(T--) 
    { 
        cin>>start>>end; 
        memset(visited, 0, sizeof(visited)); 
        BFS(); 
    } 
    return 0; 
}