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 此最相思 阅读(341) 评论(0)  编辑 收藏 引用 所属分类: bfs


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理