misschuer

常用链接

统计

积分与排名

百事通

最新评论

hdu 1195 Open the Lock

http://acm.hdu.edu.cn/showproblem.php?pid=1195

#include <iostream>
#include <queue>
using namespace std;

struct root
{
    char data[ 5 ];
    
    int step;
};

int visited[ 10000 ];

char ne[ 5 ] , ps[ 5 ];

int getdigit(char str[ ])
{
    return (str[ 0 ] - '0') * 1000 + (str[ 1 ] - '0') * 100 + (str[ 2 ] - '0') * 10 + (str[ 3 ] - '0');
}

void bfs()
{
    int i , k;
    
    char change[ 5 ] , temp;
    
    queue<root> Q;
    
    root p , q;
    
    strcpy(p.data , ne);
    
    p.step = 0;
    
    Q.push(p);
    
    while (!Q.empty())
    {
        q = Q.front();
        
        Q.pop();
        
        if(strcmp(q.data , ps) == 0)
        {
            cout << q.step << endl;
            
            break;
        }
        
        for (i = 0 ; i < 4 ; ++ i)
        {
            if (i < 3)
            {
                strcpy(change , q.data);
                
                temp = change[ i ];
                
                change[ i ] = change[i + 1];
                
                change[i + 1] = temp;
                
                k = getdigit(change);
                
                if (visited[ k ] == 0)
                {
                    visited[ k ] = 1;
                    
                    strcpy(p.data , change);
                    
                    p.step = q.step + 1;
                    
                    Q.push(p);
                }
                
                
            }
            
            
            if (q.data[ i ] == '1')
            {
                strcpy(change , q.data);
                
                change[ i ] = '9';
                
                k = getdigit(change);
                
                if (visited[ k ] == 0)
                {
                    visited[ k ] = 1;
                    
                    strcpy(p.data , change);
                    
                    p.step = q.step + 1;
                    
                    Q.push(p);
                }
                strcpy(change , q.data); 
                
                change[ i ] = '2';
                
                k = getdigit(change);
                
                if (visited[ k ] == 0)
                {
                    visited[ k ] = 1;
                    
                    strcpy(p.data , change);
                    
                    p.step = q.step + 1;
                    
                    Q.push(p);
                }
                
            }
            
            else
                if( q.data[ i ]  == '9')
                {
                    
                    strcpy(change , q.data); 
                    
                    change[ i ] = '8';
                    
                    k = getdigit(change);
                    
                    if (visited[ k ] == 0)
                    {
                        visited[ k ] = 1;
                        
                        strcpy(p.data , change);
                        
                        p.step = q.step + 1;
                        
                        Q.push(p);
                    }
                    
                    strcpy(change , q.data); 
                    
                    change[ i ] = '1';
                    
                    k = getdigit(change);
                    
                    if (visited[ k ] == 0)
                    {
                        visited[ k ] = 1;
                        
                        strcpy(p.data , change);
                        
                        p.step = q.step + 1;
                        
                        Q.push(p);
                    }
                    
                }
                
                else
                {
                    strcpy(change , q.data); 
                    
                    change[ i ] = change[ i ] - 1;
                    
                    k = getdigit(change);
                    
                    if (visited[ k ] == 0)
                    {
                        visited[ k ] = 1;
                        
                        strcpy(p.data , change);
                        
                        p.step = q.step + 1;
                        
                        Q.push(p);
                    }
                    
                    strcpy(change , q.data); 
                    
                    change[ i ] = change[ i ] + 1;
                    
                    k = getdigit(change);
                    
                    if (visited[ k ] == 0)
                    {
                        visited[ k ] = 1;
                        
                        strcpy(p.data , change);
                        
                        p.step = q.step + 1;
                        
                        Q.push(p);
                    }
                    
                }//else
                
        }//for()
        
    }//while()
    
}


int main()
{
    int t;
    
    cin >> t;
    
    while (t --)
    {
        scanf ("%s %s" , ne , ps);
        
        memset (visited , 0 , sizeof (visited));
        
        bfs();
    }
    
    return 23;
}

posted on 2009-04-19 10:42 此最相思 阅读(391) 评论(0)  编辑 收藏 引用 所属分类: bfs


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理