Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define iv pair<int, iii>
#define X first
#define Y second
using namespace std;
const int N = 2020;
const int oo = N * N;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int dd[] = {1, 2, 1, 2};
priority_queue<iv, vector<iv>, greater<iv> > Q;

int a[N][N], d[N][N][2];
int m, n;

int adj(int x, int y, int s, int xx, int yy, int ss, int dir) {
    int u = a[x][y], v = a[xx][yy];
    if (s == 1) u = 3; if (ss == 1) v = 3;
    return ((u & v & dd[dir]) == 0) ? (-1) : ss;
}

void Dijkstra() {
    d[1][n][0] = 0; d[1][n][1] = 1;
    Q.push(iv(0, iii(0, ii(1, n))));
    Q.push(iv(1, iii(1, ii(1, n))));
    int i, ux, uy, us, vx, vy, vs, du, connect; iv u;
    while (!Q.empty()) {
        u = Q.top(); Q.pop(); du = u.X;
        ux = u.Y.Y.X; uy = u.Y.Y.Y; us = u.Y.X;
        if (du != d[ux][uy][us]) continue;
        for(i = 0; i < 4; i++) {
            vx = ux + dx[i]; vy = uy + dy[i];
            if (vx < 1 || vy < 1 || vx > m || vy > n) continue;
            for(vs = 0; vs <= 1; vs++) {
                connect = adj(ux, uy, us, vx, vy, vs, i);
                if (connect == -1) continue;
                if (d[vx][vy][vs] > d[ux][uy][us] + connect) {
                    d[vx][vy][vs] = d[ux][uy][us] + connect;
                    Q.push(iv(d[vx][vy][vs], iii(vs, ii(vx, vy))));
                }
            }
        }
    }
}

int main()
{
    scanf("%d %d\n", &m, &n);
    int i, j; char ch;
    for(i = 1; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            scanf("%c", &ch);
            if (ch == '+') a[i][j] = 3; else
            if (ch == '|') a[i][j] = 1; else
            if (ch == '-') a[i][j] = 2; else
            a[i][j] = 0;
            d[i][j][0] = d[i][j][1] = oo;
        }
        scanf("\n");
    }
    Dijkstra();
    cout << min(d[m][1][0], d[m][1][1]);
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<queue>
#define MAX   2020
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define INFO(s) (s).x][(s).y][(s).t
using namespace std;
const int INF=(int)1e9+7;
char a[MAX][MAX];
int dis[MAX][MAX][2];
int m,n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct State {
    int x,y;
    bool t;
    State() {
        x=y=t=0;
    }
    State(int _x,int _y,bool _t) {
        x=_x;y=_y;t=_t;
    }
    bool canMove(int dir) const {
        if (t) return (true);
        if (a[x][y]=='+') return (true);
        if (a[x][y]=='.') return (false);
        if (a[x][y]=='-') return (dir%2==0);
        if (a[x][y]=='|') return (dir%2==1);
    }
};
void init(void) {
    scanf("%d%d",&m,&n);
    FOR(i,1,m) scanf("%s",a[i]+1);
}
bool inside(int x,int y) {
    if (x<1 || x>m || y<1 || y>n) return (false);
    return (true);
}
void bfs(void) {
    queue<State> freeQueue,costQueue;
    memset(dis,0x3f,sizeof dis);
    dis[m][1][0]=0;
    freeQueue.push(State(m,1,0));
    while (!freeQueue.empty()) {
        while (!freeQueue.empty()) {
            State u=freeQueue.front();freeQueue.pop();
            costQueue.push(u);
            REP(i,4) if (inside(u.x+dx[i],u.y+dy[i])) {
                State v(u.x+dx[i],u.y+dy[i],0);
                if (u.canMove(i) && v.canMove(i) && dis[INFO(v)]>=INF) {
                    dis[INFO(v)]=dis[INFO(u)];
                    freeQueue.push(v);
                }
            }
        }
        while (!costQueue.empty()) {
            State u=costQueue.front();costQueue.pop();
            REP(i,4) if (inside(u.x+dx[i],u.y+dy[i])) {
                State v(u.x+dx[i],u.y+dy[i],1);
                if (u.canMove(i) && v.canMove(i) && dis[INFO(v)]>=INF) {
                    dis[INFO(v)]=dis[INFO(u)]+1;
                    freeQueue.push(v);
                }
            }
            if (!u.t && dis[u.x][u.y][1]>=INF) {
                dis[u.x][u.y][1]=dis[INFO(u)]+1;
                freeQueue.push(State(u.x,u.y,1));
            }
        }
    }
    printf("%d\n",min(dis[1][n][0],dis[1][n][1]));
}
int main(void) {
    init();
    bfs();
    return 0;
}