E – Bishop 2

题目描述：

给你一个n * n的矩阵，起点和终点确定，你只能沿对角线走，走的距离可以任意，但是从(x1, y1)走到(x2, y2)的过程中不能存在障碍物，且坐标必须合法，问最下需要几步能到达

思路：

经典bfs，第一反应是暴力bfs，四个方向，每个方向最多走n米…

这个题给了6秒，确实可以卡过去，不过很难卡:(

这个题可以用01bfs来做,,每个点只需要扩展四周的点然后记录扩展的方向,如果方向相同那么边权就是0,方向不同边权就是1

注意vis数组也要开四个状态进行记录！！！

暴力的bfs：

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1500 + 50
int n, m, k;
int sx, sy, ex, ey;
char tr[MAX][MAX];

int dx[] = {1, 1, -1, -1};
int dy[] = {1, -1, 1, -1};
bool vis[MAX][MAX];
int ans[MAX][MAX];
pii q[5000000];

void bfs(){
    int fr = -1, ed = 0;
    q[++fr] = m_p(sx, sy);
    ans[sx][sy] = 0;
    while (ed <= fr) {
        auto now = q[ed++];
        if(now.first == ex && now.second == ey){
            cout << ans[ex][ey] << endl;
            return;
        }
        vis[now.first][now.second] = 1;
        for(int i = 0; i < 4; ++i){
            for(pii st = {now.first + dx[i], now.second + dy[i]};;st.first += dx[i], st.second += dy[i]){
                if(st.first > n || st.first < 1 ||
                   st.second > n || st.second < 1||
                   vis[st.first][st.second]||
                   tr[st.first][st.second] == '#')break;
                if(ans[st.first][st.second] != -1)continue;
                ans[st.first][st.second] = ans[now.first][now.second] + 1;
                q[++fr] = st;
            }
        }
    }
    cout << -1 << endl;
}

void work(){
    cin >> n;
    mem(ans, -1);
    cin >> sx >> sy >> ex >> ey;
    if(sx + sy + ex + ey & 1){
        puts("-1");
        return;
    }
    for(int i = 1; i <= n; ++i)scanf("%s", tr[i] + 1);
    bfs();
}


int main(){
    work();
    return 0;
}

优美的01bfs

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1500 + 50
int n, m, k;
char tr[MAX][MAX];
int sx, sy, ex, ey;

int dx[] = {1, 1, -1, -1};
int dy[] = {1, -1, 1, -1};

struct ran{
    int op, x, y, step;
};
bool vis[MAX][MAX][4];
bool judge(int x, int y, int op){
    if(x > n || x < 1 || y > n || y < 1)return false;
    else if(vis[x][y][op])return false;
    else if(tr[x][y] == '#')return false;
    else return true;
}
void bfs(){
    deque<ran>q;
    q.push_back({-1, sx, sy, 0});
    while (!q.empty()) {
        auto [op, x, y, step] = q.front();q.pop_front();
        if(x == ex && y == ey){
            cout << step << endl;
            return;
        }
        for(int i = 0; i < 4; ++i){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(!judge(xx, yy, i))continue;
            vis[x][y][op] = 1;
            if(i == op)q.push_front({i, xx, yy, step});
            else q.push_back({i, xx, yy, step + 1});
        }
    }
    cout << -1 << endl;
}

void work(){
    cin >> n >> sx >> sy >> ex >> ey;
    if(sx + sy + ex + ey & 1){
        cout << -1 << endl;
        return;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> tr[i][j];
        }
    }
    bfs();
}

int main(){
    io;
    work();
    return 0;
}