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 <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

string a[1010], s;
int m, n, sx, sy, dist[1010][1010];
vector < pair <int,int> > q[1000100];
queue <int> id[8];

int main()
{
    cin >> m >> n >> sx >> sy;
    for (int i = 0; i < m; i++) cin >> a[i];
    cin >> s;

    memset(dist, -1, sizeof dist);
    q[0].push_back(make_pair(--sx, --sy));
    dist[sx][sy] = 0;

    for (int i = 0; i < int(s.size()); i++) id[s[i] - '1'].push(i);

    for (int day = 0; day < int(s.size()); day++)
        for (int i = 0; i < int(q[day].size()); i++)
        {
            int x = q[day][i].first, y = q[day][i].second;
            if (dist[x][y] != day) continue;

            for (int j = 0; j < 8; j++)
            {
                int nextDay = -1;
                while (!id[j].empty())
                    if (id[j].front() < day) id[j].pop();
                    else
                    {
                        nextDay = id[j].front();
                        break;
                    }

                if (nextDay < 0) continue;

                int xx = x + dx[j], yy = y + dy[j];
                if (xx >= 0 && xx < m && yy >= 0 && yy < n && a[xx][yy] == '.')
                    if (dist[xx][yy] < 0 || dist[xx][yy] > nextDay + 1)
                    {
                        dist[xx][yy] = nextDay + 1;
                        q[dist[xx][yy]].push_back(make_pair(xx, yy));
                    }
            }
        }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++) cout << (dist[i][j] >= 0);
        cout << "\n";
    }
}

Code mẫu của happyboy99x

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int L = 1e6, M = 1e3;
const int delta[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; 
int next[L + 1][8], d[M][M], m, n, sx, sy;
string s, mat[M];

int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n >> sx >> sy; --sx; --sy;
    for(int i = 0; i < m; ++i)
        cin >> mat[i];
    cin >> s;
    int len = s.size();
    fill_n(next[len], 8, -1);
    for(int i = len - 1; i >= 0; --i) {
        copy(next[i + 1], next[i + 1] + 8, next[i]);
        next[i][s[i] - '0' - 1] = i;
    }
    memset(d, 0x3f, sizeof d);
    priority_queue<pair<int, pair<int, int> > > q;
    q.push(make_pair(0, make_pair(sx, sy))); d[sx][sy] = 0;
    while(!q.empty()) {
        int duv = -q.top().first, u = q.top().second.first, v = q.top().second.second; q.pop();
        if(duv > d[u][v]) continue;
        for(int k = 0; k < 8; ++k) if(next[duv][k] != -1) {
            int x = u + delta[k][0], y = v + delta[k][1];
            if(x >= 0 && x < m && y >= 0 && y < n && mat[x][y] != '#' && d[x][y] > next[duv][k] + 1) {
                d[x][y] = next[duv][k] + 1;
                q.push(make_pair(-d[x][y], make_pair(x, y)));
            }
        }
    }
    string res;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j)
            res += d[i][j] <= len ? '1' : '0';
        res += '\n';
    }
    cout << res << endl;
    return 0;
}

Code mẫu của ladpro98

program VOBOARD2;
uses    math;
type    e=record
        x,y:longint;
        end;
const   fi='';
        fo='';
        maxn=1001;
        maxQ=sqr(maxn);
        dx:array['1'..'8'] of longint = (-1,-1,0,1,1,1,0,-1);
        dy:array['1'..'8'] of longint = (0,1,1,1,0,-1,-1,-1);
var     a:array[1..maxn,1..maxn] of longint;
        m,n,u,v,l,r,layer,nq,d:longint;
        q,q2:array[0..maxQ] of e;
        check,check2:array[1..maxn,1..maxn] of boolean;
        s:ansistring;

procedure input;
var     inp:text;
        i,j:longint;
        c:char;
begin
        assign(inp,fi);reset(inp);
        readln(inp,m,n);
        readln(inp,u,v);
        for i:=1 to m do
        begin
                for j:=1 to n do
                begin
                        read(inp,c);
                        if c='#' then a[i,j]:=1;
                end;
                readln(inp);
        end;
        readln(inp,s);
        close(inp);
end;

procedure play(x,y:longint);
begin
        if (1<=x) and (x<=m) and (1<=y) and (y<=n) and (a[x,y]=0) and (not check[x,y]) then
        begin
                check[x,y]:=true;
                check2[x,y]:=true;
                inc(d);
                q2[d].x:=x;
                q2[d].y:=y;
        end;
end;

function ok(x,y:longint):boolean;
var     i:char;
        xx,yy:longint;
begin
        for i:='1' to '8' do
        begin
                xx:=x+dx[i];
                yy:=y+dy[i];
                if (1<=xx) and (xx<=m) and (1<=yy) and (yy<=n)
                and (a[xx,yy]=0) and (not check2[xx,yy]) then
                exit(true);
        end;
        exit(false);
end;

procedure bfs;
var     u:e;
        i:longint;
begin
        d:=0;
        while nq>0 do
        begin
                u:=q[l];
                l:=(l+1) mod maxQ;
                dec(nq);
                play(u.x,u.y);
                play(u.x+dx[s[layer]],u.y+dy[s[layer]]);
        end;
        for i:=1 to d do
        if ok(q2[i].x,q2[i].y) then
        begin
                r:=(r+1) mod maxQ;
                inc(nq);
                q[r]:=q2[i];
        end;
end;

procedure process;
var     i:longint;
begin
        l:=1;r:=1;
        nq:=1;
        q[1].x:=u;
        q[1].y:=v;
        for layer:=1 to length(s) do
        begin
                bfs;
                if layer<length(s) then
                for i:=1 to d do
                check[q2[i].x,q2[i].y]:=false;
        end;
end;

procedure output;
var     i,j:longint;
        oup:text;
begin
        assign(oup,fo);rewrite(oup);
        for i:=1 to m do
        begin
                for j:=1 to n do
                if check2[i,j] then write(oup,1)
                else write(oup,0);
                writeln(oup);
        end;
        close(oup);
end;

begin
        input;
        process;
        output;
end.

Code mẫu của RR

// Author: RR
// Expected score: 100

#include <bits/stdc++.h>

#define DEBUG(x) { cout << #x << " = " << x << endl; }
using namespace std;

const int MN = 1000;
const int oo = 1000111000;

int m, n, startu, startv, l;
char a[MN + 11][MN + 11], s[MN*MN + 11], tmp[MN + 11];
set< pair<int, pair<int,int> > > nodes;
int d[MN + 11][MN + 11];
int next[MN*MN + 11][10];

void readInput() {
    scanf("%d %d\n", &m, &n);
    assert(1 <= m && m <= MN && 1 <= n && n <= MN);

    scanf("%d %d\n", &startu, &startv);
    assert(1 <= startu && startu <= m && 1 <= startv && startv <= n);

    for(int i = 1; i <= m; ++i) {
        gets(tmp);
        assert(strlen(tmp) == n);

        for(int j = 1; j <= n; ++j) {
            a[i][j] = tmp[j-1];
            assert(a[i][j] == '#' || a[i][j] == '.');
        }
    }

    assert(a[startu][startv] == '.');

    gets(s);
    l = strlen(s);
    assert(1 <= l && l <= MN*MN);
    for(int i = 0; i < l; ++i)
        assert(s[i] >= '1' && s[i] <= '8');
}

void init() {
    for(int i = l; i >= 0; --i) {
        if (i == l) {
            for(int c = 1; c <= 8; ++c)
                next[i][c] = oo;
        }
        else {
            for(int c = 1; c <= 8; ++c)
                next[i][c] = next[i+1][c];
            next[i][s[i]-'0'] = i+1;
        }
    }
}

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

void solve() {
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            d[i][j] = oo;

    d[startu][startv] = 0;
    nodes.insert(make_pair(0, make_pair(startu, startv)));
    while (!nodes.empty()) {
        int len = nodes.begin()->first;
        int u = nodes.begin()->second.first, v = nodes.begin()->second.second;
        nodes.erase(nodes.begin());
        if (len != d[u][v]) continue;

        if (len == l) continue;

        for(int dir = 1; dir <= 8; ++dir) {
            int uu = u + di[dir], vv = v + dj[dir];
            if (uu < 1 || uu > m || vv < 1 || vv > n || a[uu][vv] == '#') continue;
            if (d[uu][vv] <= next[len][dir]) continue;

            d[uu][vv] = next[len][dir];
            nodes.insert(make_pair(d[uu][vv], make_pair(uu, vv)));
        }
    }
    int cnt = 0;
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j)
            if (d[i][j] <= l) {
                putchar('1');
                ++cnt;
            }
            else putchar('0');
        puts("");
    }
    cerr << cnt << " / " << m * n << endl;
}

int main() {
    readInput();
    init();
    solve();
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<queue>
#define MAX   1010
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define fi   first
#define se   second
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> pii;
char a[MAX][MAX];
int d[MAX][MAX];
char cmd[MAX*MAX];
int next[MAX*MAX][9];
int m,n,l,sx,sy;
int dx[]={0,-1,-1,0,1,1,1,0,-1};
int dy[]={0,0,1,1,1,0,-1,-1,-1};
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    scanf("%d",&sx);
    scanf("%d",&sy);
    FOR(i,1,m) scanf("%s",a[i]+1);
    scanf("%s",cmd+1);
    l=strlen(cmd+1);
    REP(i,9) next[l][i]=l+1;
    FORD(i,l-1,0) {
        REP(j,9) next[i][j]=next[i+1][j];
        next[i][cmd[i+1]-48]=i+1;
    }
}
bool canmove(int x,int y) {
    if (x<1) return (false);
    if (y<1) return (false);    
    if (x>m) return (false);
    if (y>n) return (false);
    return (a[x][y]=='.');
}
void dijkstra(void) {
    priority_queue<pii,vector<pii>,greater<pii> > q;
    while (!q.empty()) q.pop();
    memset(d,0x3f,sizeof d);
    d[sx][sy]=0;
    q.push(pii(0,ii(sx,sy)));
    while (!q.empty()) {
        pii u=q.top();q.pop();
        FOR(i,1,8) if (next[u.fi][i]<=l)
            if (canmove(u.se.fi+dx[i],u.se.se+dy[i]))
                if (d[u.se.fi+dx[i]][u.se.se+dy[i]]>next[u.fi][i]) {
                    d[u.se.fi+dx[i]][u.se.se+dy[i]]=next[u.fi][i];
                    q.push(pii(next[u.fi][i],ii(u.se.fi+dx[i],u.se.se+dy[i])));
                }
    }
}
void print(void) {
    FOR(i,1,m) {
        FOR(j,1,n) {
            if (d[i][j]<=l) printf("1");
            else printf("0");
        }
        printf("\n");
    }
}
int main(void) {
    init();
    dijkstra();
    print();
    return 0;
}