misschuer

公告

留言簿

隨筆分類

文章分類

acm (rss)
Java (rss)

隨筆檔案

文章檔案

2009年4月 (1)

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 61
文章 - 1
評論 - 18
引用 - 0

積分與排名

積分 - 25150
排名 - 726

百事通

hao123
WPL
杭電
松松
星和

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 此最相思閱讀(374) 評論(0) 編輯收藏引用所屬分類: bfs

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

misschuer

導航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

積分與排名

百事通

最新評論

hdu 1195 Open the Lock