题解 P1126 【机器人搬重物】
林则徐
2017-12-15 23:01:22
一道典型的广搜题，注意以下两点即可：
1. 机器人有体积，bfs时可以将机器人的坐标，这样判断障碍物较为方便。
2. 已经访问过的位置（包括横坐标，纵坐标及方向）不可重复访问，可用一个辅助数组来判重。
附上代码：
```cpp
#include<cstdio>
#include<cstdlib>
#include<queue>
#define For(a,b,c,d) for(register int a=b;a<=c;a+=d)
const int my[ 4 ] = { 0 , 1 , 0 , -1 } , mx[ 4 ] = { -1 , 0 , 1 , 0 } ; //每个方向的移动规则
int n , m , maze[ 60 ][ 60 ] ;
bool vis[ 20000 ] ; //记录访问过的位置
inline int fun( int a , int b , int c ) { return c * 2700 + a * 51 + b ;} //返回每种情况唯一对应的key值
struct pos { //每个位置的信息
int x , y ; //坐标
int f ; //方向
int mov ; //已移动时间
} ;
std::queue<pos> que ;
inline bool zq( int x , int y ) { //判断是否撞上障碍物
if( maze[ x ][ y ] || maze[ x + 1 ][ y ] || maze[ x ][ y + 1 ] || maze[ x + 1 ][ y + 1 ] )
return 1 ;
return 0 ;
}
inline void bfs() {
int x , y , tx , ty , f , d , mov , lx , ly ;
char c ;
scanf("%d %d %d %d %c" , &x , &y , &tx , &ty , &c );
switch( c ) {
case 'N': f = 0 ;
break ;
case 'E': f = 1 ;
break ;
case 'S': f = 2 ;
break ;
case 'W': f = 3 ;
break ;
}
pos temp ;
temp.x = x , temp.y = y , temp.f = f , temp.mov = 0 ;
que.push( temp ) ;
while( !que.empty() ) {
temp = que.front() ;
que.pop() ;
x = temp.x , y = temp.y , f = temp.f , d = fun( x , y , f ) , mov = temp.mov ;
if( x == tx && y == ty ) { //判断是否是重点
printf("%d",mov) ;
exit( 0 ) ;
}
if( vis[ d ] ) //判断是否被访问过
continue ;
vis[ d ] = 1 ;
temp.mov ++ ;
temp.f = ( f + 4 - 1 ) % 4 ; //左转
que.push( temp ) ;
temp.f = ( f + 4 + 1 ) % 4 ; //右转
que.push( temp ) ;
temp.f = f ;
For( i , 1 , 3 , 1 ) { //向前移动
lx = x + mx[ f ] * i , ly = y + my[ f ] * i ;
if( lx <= 0 || ly <= 0 || lx >= n || ly >= m || zq( lx , ly ) )
break ;
temp.x = lx ;
temp.y = ly ;
que.push( temp ) ;
}
}
printf("-1");
}
int main() { //主函数
scanf("%d %d" , &n , &m ) ;
For( i , 1 , n , 1 ) {
For( j , 1 , m , 1 ) {
scanf("%d", &maze[ i ][ j ] );
}
}
bfs() ;
return 0;
}
```