本文主要是介绍POJ 1376 Robot——C++的BFS解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目传送门：http://poj.org/problem?id=1376
洛谷翻译传送门：https://www.luogu.org/problemnew/show/P1126
注：POJ是多组输入，洛谷是单组输入。
『解题思路』
采用BFS策略求从起点到终点的最短路，题目有点坑，输入的是方格坐标，但机器人移动的是点，应该注意。因为还有方向问题，故而首先将方向转化为数字变量，便于计算旋转的步数。
north —— 0；east —— 1；south —— 2；west —— 3；
因为步长有三种选择1,2,3，所以应该使用循环找出到转折点最小的步数，然后将转折点存入队列中，进行下一次搜索。
『代码』
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#define For(a,b,c,d) for(register int a=b;a<=c;a+=d)
using namespace std;
int my[ 4 ] = { 0 , 1 , 0 , -1 } , mx[ 4 ] = { -1 , 0 , 1 , 0 } ;
int n , m , maze[ 55 ][ 55 ] ;
bool vis[ 20000 ] ;
//压缩
int fun( int a , int b , int c ) {return c * 2700 + a * 51 + b ;
}
struct Node {int x , y ;int f ;int mov ;
} ;
queue<Node> que ;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 ;
}void bfs() {string str;int x , y , tx , ty , f , d , mov , lx , ly ;char c[10];scanf("%d %d %d %d %s" , &x , &y , &tx , &ty , c );str = c;if(str == "north")//将方向转换为数字 f = 0 ;else if(str == "east")f = 1;else if(str == "south")f = 2;else if(str == "west")f = 3;Node 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\n",mov) ;return ;}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\n");
}
int main() {while(scanf("%d %d" , &n , &m )) {memset(vis,0,sizeof(vis)); if(n == 0 && m == 0)break;For( i , 1 , n , 1 ) {For( j , 1 , m , 1 ) {scanf("%d", &maze[ i ][ j ] );}}while(!que.empty()){que.pop();}bfs() ;}return 0;
}
这篇关于POJ 1376 Robot——C++的BFS解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
