---

title: "bfs + 模拟"
author: Sun-Wind
date: January 29,2022

凡是涉及到模拟的一般坑也会比较多，在这道题我遇到的坑包括但不限于

• 判断每一步的障碍，并且在判断到障碍后直接跳出，不能继续向前
• 这个球是有体积的，也就是说题目中给我们的只是他边角上的一个点，还需要判断其他4个点是否符合要求
• 注意有可能起始坐标和终点坐标相同

#include<iostream>
#include<utility>
#include<queue>
using namespace std;
typedef long long ll;
#define fi(i,a,b) for(int i = a; i <= b; ++i)
#define fr(i,a,b) for(int i = a; i >= b; --i)
#define x first
#define y second
#define sz(x) ((int)(x).size())
#define pb push_back
using pii = pair<int,int>;
//#define DEBUG
int thing[55][55];
int dir[4] = {0,1,2,3};//表示方向
struct point{
    int x,y,step;
    int state;
};
int start_x,start_y,end_x,end_y;
char temp;
int res;
int n,m;
bool vis[55][55][4];
queue<point> que;
bool check(int p,int q){
    if(thing[p][q]) return false;
    if(p + 1 <= n){
        if(thing[p+1][q]) return false;
        if(q + 1 <= m){
            if(thing[p+1][q+1]) return false;
        }
        else return false;
    }
    else return false;
    if(q + 1 <= m){
        if(thing[p][q+1]) return false;
    }
    else return false;
    return true;
}
int bfs(){
    queue<point> que;
    que.push({start_x,start_y,0,res});
    vis[start_x][start_y][res] = true;
    while(!que.empty()){
        point temp = que.front();
        que.pop();
        fi(i,1,3){
            if(temp.state == 0){
                int p = temp.x;
                int q = temp.y + i;
                if(q < 1 || q > m) continue;
                if(!vis[p][q][0]){
                    if(!check(p,q)){
                        // vis[p][q][0] = true;
                        break;
                    }
                    // cout << p <<" " <<  q << " " << temp.step+1;
                    // cout << endl;
                    if(p == end_x && q == end_y)
                        return temp.step + 1;
                    que.push({p,q,temp.step+1,0});
                    vis[p][q][0] = true;
                }
            }
            else if(temp.state == 1){
                int p = temp.x + i;
                int q = temp.y;
                if(p < 1 || p > n) continue;
                if(!vis[p][q][1]){
                    if(!check(p,q)){
                        // vis[p][q][1] = true;
                        break;
                    }
                    // cout << p <<" " <<  q << " " << temp.step+1;
                    // cout << endl;
                    if(p == end_x && q == end_y)
                        return temp.step + 1;
                    que.push({p,q,temp.step+1,1});
                    vis[p][q][1] = true;
                }
            }
            else if(temp.state == 2){
                int p = temp.x;
                int q = temp.y - i;
                if(q < 1 || q > m) continue;
                if(!vis[p][q][2]){
                    if(!check(p,q)){
                        // vis[p][q][2] = true;
                        break;
                    }
                    // cout << p <<" " <<  q << " " << temp.step+1;
                    // cout << endl;
                    if(p == end_x && q == end_y)
                        return temp.step + 1;
                    que.push({p,q,temp.step+1,2});
                    vis[p][q][2] = true;
                }
            }
            else if(temp.state == 3){
                int p = temp.x - i;
                int q = temp.y;
                if(p < 1 || p > n) continue;
                if(!vis[p][q][3]){
                    if(!check(p,q)){
                        // vis[p][q][3] = true;
                        break;
                    }
                    // cout << p <<" " <<  q << " " << temp.step+1;
                    // cout << endl;
                    if(p == end_x && q == end_y)
                        return temp.step + 1;
                    que.push({p,q,temp.step+1,3});
                    vis[p][q][3] = true;
                }
            }
        }
        fi(i,1,3){
            if(i == 2) continue;
            int p = (temp.state + i) % 4;
            if(!vis[temp.x][temp.y][p])
                {
                    que.push({temp.x,temp.y,temp.step+1,p});
                    vis[temp.x][temp.y][p] = true;
                }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    fi(i,1,n) fi(j,1,m)
    cin >> thing[i][j];
    cin >> start_x >> start_y >> end_x >> end_y;
    if(start_x == end_x && start_y == end_y) {
        cout << 0 << endl;
        return 0;
    }
    cin >> temp;
    if(temp == 'E') res = 0;
    else if(temp == 'S') res = 1;
    else if(temp == 'W') res = 2;
    else res = 3;
    cout << bfs() << endl;
#ifdef DEBUG
    //freopen(D:\in.txt,r,stdin);
#endif
    return 0;
}