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 flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <queue>
#include <utility>
#define N 707
#define oo 1000000
using namespace std;
const int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};

int m,n,deadline[N][N],youTime[N][N],vikingTime[N][N];
pair <int,int> viking,treasure,you;
int top[N][N],bot[N][N],lef[N][N],rig[N][N];
string a[N];
queue < pair<int,int> > q;
int cnt;
void init()
{
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
        {
            deadline[i][j]=youTime[i][j]=vikingTime[i][j]=oo;
            top[i][j]=i-1; bot[i][j]=i+1;
            lef[i][j]=j-1; rig[i][j]=j+1;
        }
}

int shootVer(int f[N][N],int g[N][N],int x,int y,int v,int u)
{
    g[x][y]=u;
    if (!x || x>m || a[x][y]=='I') return x;
    if (deadline[x][y]>v) deadline[x][y]=v;
    return f[x][y]=shootVer(f,g,f[x][y],y,v,u);
}

int shootHor(int f[N][N],int g[N][N],int x,int y,int v,int u)
{
    g[x][y]=u;
    if (!y || y>n || a[x][y]=='I') return y;
    if (deadline[x][y]>v) deadline[x][y]=v;
    return f[x][y]=shootHor(f,g,x,f[x][y],v,u);
}

void vikingMove(int x,int y)
{
    while (!q.empty()) q.pop();
    q.push(make_pair(x,y));
    vikingTime[x][y]=0;
    while (!q.empty())
    {
        x=q.front().first; y=q.front().second; q.pop();
        shootVer(top,bot,x,y,vikingTime[x][y],bot[x][y]);
        shootVer(bot,top,x,y,vikingTime[x][y],top[x][y]);
        shootHor(lef,rig,x,y,vikingTime[x][y],rig[x][y]);
        shootHor(rig,lef,x,y,vikingTime[x][y],lef[x][y]);
        for (int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if (xx && yy && xx<=m && yy<=n && a[xx][yy]!='I' && vikingTime[xx][yy]==oo)
            {
                vikingTime[xx][yy]=vikingTime[x][y]+1;
                q.push(make_pair(xx,yy));
            }
        }
    }       
}

int richAndAlive(int x,int y)
{
    while (!q.empty()) q.pop();
    q.push(make_pair(x,y));
    youTime[x][y]=0;
    while (!q.empty())
    {
        pair <int,int> u=q.front(); q.pop();
        int x=u.first,y=u.second;
        if (youTime[x][y]>=deadline[x][y] && youTime[x][y]) continue;
        if (u==treasure) return 1;
        for (int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if (xx && yy && xx<=m && yy<=n && a[xx][yy]!='I' && youTime[xx][yy]==oo)
            {
                youTime[xx][yy]=youTime[x][y]+1;
                q.push(make_pair(xx,yy));
            }
        }
    }
    return 0;       
}

int main()
{
    cin >> m >> n;
    for (int i=1;i<=m;i++)
    {
        cin >> a[i];
        a[i]="*"+a[i];
        for (int j=1;j<=n;j++)
        {
            if (a[i][j]=='V') viking=make_pair(i,j);
            if (a[i][j]=='T') treasure=make_pair(i,j);
            if (a[i][j]=='Y') you=make_pair(i,j);
        }
    }
    init();
    vikingMove(viking.first,viking.second);
    puts(richAndAlive(you.first,you.second)?"YES":"NO");
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
using namespace std;

const int MN = 1011;

int m, n, row[MN][MN], col[MN][MN], drow[MN*MN], dcol[MN*MN];
char a[MN][MN];
queue< pair<int,int> > q;
int d[MN][MN];

bool check(char c) {
    return c && c != 'I';
}

void init() {
    int now = 0;
    FOR(i,1,m) FOR(j,1,n)
    if (a[i][j] != 'I') {
        if (check(a[i][j-1])) row[i][j] = row[i][j-1];
        else {
            row[i][j] = ++now;
            drow[now] = 1000111000;
        }
    }

    now = 0;
    FOR(j,1,n) FOR(i,1,m)
    if (a[i][j] != 'I') {
        if (check(a[i-1][j])) col[i][j] = col[i-1][j];
        else {
            col[i][j] = ++now;
            dcol[now] = 1000111000;
        }
    }
}

const int di[] = {-1,1,0,0};
const int dj[] = {0,0,-1,1};

bool outside(pair<int,int> v) {
    if (v.F < 1 || v.S < 1 || v.F > m || v.S > n) return true;
    return false;
}

void bfs(int startu, int startv, bool block) {
    while (!q.empty()) q.pop();
    memset(d, -1, sizeof d);
    d[startu][startv] = 0;
    q.push(MP(startu, startv));

    while (!q.empty()) {
        pair<int,int> u = q.front(); q.pop();
        REP(dir,4) {
            pair<int,int> v = MP(u.F + di[dir], u.S + dj[dir]);
            if (outside(v) || a[v.F][v.S] == 'I') continue;
            if (d[v.F][v.S] >= 0) continue;

            if (block &&
                (d[u.F][u.S] + 1 >= min(dcol[col[v.F][v.S]], drow[row[v.F][v.S]]))) continue;

            d[v.F][v.S] = d[u.F][u.S] + 1;
            q.push(v);
        }
    }
}

int main() {
    scanf("%d%d\n", &m, &n);
    FOR(i,1,m) {
        scanf("%s\n", &a[i][1]);
    }
    init();
    FOR(i,1,m) FOR(j,1,n) if (a[i][j] == 'V') {
        bfs(i,j,false);
    }
    FOR(i,1,m) FOR(j,1,n)
    if (a[i][j] != 'I') {
        int r = row[i][j], c = col[i][j];
        drow[r] = min(drow[r], d[i][j]);
        dcol[c] = min(dcol[c], d[i][j]);
    }
    FOR(i,1,m) FOR(j,1,n)
    if (a[i][j] == 'Y') {
        bfs(i,j,true);
    }
    FOR(i,1,m) FOR(j,1,n)
    if (a[i][j] == 'T') {
        if (d[i][j] >= 0) puts("YES");
        else puts("NO");
    }
    return 0;
}