題意:
有個機器人會在格線上行走,然後有個地圖,格點會有建築物;若那個個點有建築物(1),那機器人就不行經過他四周的格線
機器人有兩種移動方式,都只要一秒
1. 向左或向右轉90度
2.向目前方向走1~3格
問說機器人從起點走到終點最少需要幾秒,走不到的話輸出-1
解法:
把每格多拆成四格(四個方向)做BFS,每個點可以左轉右轉以及前進1~3格
要注意的是邊界問題,地圖中最外圍的那圈是不行走的
另外還有就是步行跳過去格子,若往前走一步不行的話,那你就不行往前走兩步或三步
程式碼:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX(x,y)( ((x)>(y))?(x):(y))
char map[123][123];
char v[123][123][4];
int n,m;
int s[2],e[2];
int q[123456][3];
int qNum;
int dir[128]={0};
int move[4][2] = { {-1,0},{0,-1},{1,0},{0,1} };
int turn[2] = {1,3};
int BFS(int s[],int e[],int dir){
if(s[0]==e[0] && s[1]==e[1])return 0;
int i,j;
int x,y,d;
int nx,ny,nd;
memset(v,-1,sizeof(v));
q[0][0] = s[0];
q[0][1] = s[1];
q[0][2] = dir;
qNum = 1;
v[q[0][0]][q[0][1]][q[0][2]] = 0;
for(i=0;i<qNum;++i){
x = q[i][0];
y = q[i][1];
d = q[i][2];
for(j=0;j<2;++j){
nd = (d+turn[j])%4;
if(v[x][y][nd]==-1){
v[x][y][nd] = v[x][y][d]+1;
q[qNum][0] = x;
q[qNum][1] = y;
q[qNum][2] = nd;
++qNum;
}
}
for(j=1,nx=x,ny=y;j<=3;++j){
nx += move[d][0];
ny += move[d][1];
if(nx<1||ny<1||nx>=n||ny>=m|| map[nx][ny])break;
if(v[nx][ny][d]!=-1 )continue;
if(nx==e[0]&&ny==e[1]) return v[x][y][d]+1;
q[qNum][0] = nx;
q[qNum][1] = ny;
q[qNum][2] = d;
v[nx][ny][d] = v[x][y][d]+1;
++qNum;
}
}
return -1;
}
int main(){
int i,j;
int tmp;
char str[123];
dir['n'] = 0;
dir['w'] = 1;
dir['s'] = 2;
dir['e'] = 3;
while(scanf("%d %d",&n,&m)!=EOF &&(n|m)){
memset(map,0,sizeof(map));
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
scanf("%d",&tmp);
if(tmp){
map[i][j] = 1;
map[i-1][j] = 1;
map[i][j-1] = 1;
map[i-1][j-1] = 1;
}
}
}
scanf("%d %d %d %d %s",&s[0],&s[1],&e[0],&e[1],str);
printf("%d\n",BFS(s,e,dir[(int)(str[0])]));
}
return 0;
}
留言列表