BZOJ 1054: [HAOI2008]移动玩具( BFS )

浏览数：23 / 时间：2015年06月11日

技术分享

一开始没有注意答案为0的情况然后就WA了...

挺水的BFS.. 

------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#include<iostream>
 
#define rep( i , n ) for( int i = 0 ; i < n ; ++i )
#define clr( x , c ) memset( x , c , sizeof( x ) )
 
using namespace std;
 
const int N = 4;
const int dir[ 4 ][ 2 ] = { { 0 , 1 } , { 0 , -1 } , { 1 , 0 } , { -1 , 0 } };
 
bool a[ N ][ N ];
 
int encode() {
int ans = 0;
int p = 15;
rep( i , N )
   rep( j , N ) {
    if( a[ i ][ j ] ) ans |= 1 << p;
    p--;
   }
return ans;
}
 
void decode( int code ) {
int p = 15;
rep( i , N )
   rep( j , N ) {
       a[ i ][ j ] = ( code & ( 1 << p ) ? true : false );
       p--;
   }
}
 
#define ok( x , y ) ( x >= 0 && x < 4 && y >= 0 && y < 4 )
 
int goal , start;
 
void Read() {
rep( i , N )
   rep( j , N ) {
    char c = getchar();
    while( ! isdigit( c ) ) c = getchar();
    a[ i ][ j ] = c - ‘0‘;
   }
start = encode();
rep( i , N )
   rep( j , N ) {
    char c = getchar();
    while( !isdigit( c ) ) c = getchar();
    a[ i ][ j ] = c - ‘0‘;
   }
goal = encode();
}
 
queue< pair< int , int > > Q;
bool S[ 1 << 16 ];
 
int BFS() {
if( start == goal ) return 0;
clr( S , 0 );
Q.push( make_pair( start , 0 ) );
while( ! Q.empty() ) {
int x = Q.front().first , d = Q.front().second;
Q.pop();
decode( x );
rep( i , N ) 
   rep( j , N ) if( a[ i ][ j ] )
    rep( k , 4 ) {
   
    int X = i + dir[ k ][ 0 ] , Y = j + dir[ k ][ 1 ];
   
    if( a[ X ][ Y ] || ! ok( X , Y ) ) continue;
   
    a[ i ][ j ] = false;
    a[ X ][ Y ] = true;
   
    int s = encode();
   
    if( s == goal ) return d + 1;
   
    if( ! S[ s ] ) {
    Q.push( make_pair( s , d + 1 ) );
    S[ s ] = true;
    }
   
    a[ i ][ j ] = true;
    a[ X ][ Y ] = false;
   
    }
}
   
}
int main() {
Read();
cout << BFS() << "\n";
return 0;
}

 

------------------------------------------------------------------------------

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1301  Solved: 715
[Submit][Status][Discuss]

Description

在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

Input

前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。

Output

一个整数，所需要的最少移动次数。

Sample Input

1111
0000
1110
0010

1010
0101
1010
0101

Sample Output

4

HINT

Source

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢