程式碼備份區

題意：

有個機器人會在格線上行走，然後有個地圖，格點會有建築物；若那個個點有建築物(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;
}