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 <vector>
#include <cstring>
using namespace std;

int m,n,sm,cnt,last,c[20010],d[20010],low[20010],num[20010],st[20010];
int f[20010],val[20010],vs[20010];
vector <int> a[20010],b[20010];
char s[10011];

void visit(int x)
{
    low[x]=num[x]=++cnt; st[++last]=x;
    for (int i=0;i<int(a[x].size());i++)
    {
        int y=a[x][i];
        if (!d[y])
        {
            if (num[y]) low[x]=min(low[x],num[y]);
            else 
            {
                visit(y);
                low[x]=min(low[x],low[y]);
            }
        }
    }
    if (low[x]!=num[x]) return;
    sm++;
    while (1)
    {
        int i=st[last--];
        d[i]=sm;
        val[sm]+=c[i];
        if (i==x) return;
    }
}

void calc(int x)
{
    vs[x]=1;
    for (int i=0;i<int(b[x].size());i++)
    {
        int y=b[x][i];
        if (!vs[y]) calc(y);
        f[x]=max(f[x],f[y]);
    }
    f[x]+=val[x];
}

int main()
{
    //freopen("in","r",stdin);
    char t[10100],ss[10100];
    cin >> m >> n;
    gets(t); 
    for (int i=1;i<=m;i++) 
    {
        scanf("%s",&ss);
        int l=strlen(ss);
        for (int j=0;j<n;j++) s[j]=(j<l?ss[j]:'0');
        for (int j=1;j<=n;j++)
        {
            int x=(i-1)*n+j;
            if (s[j-1]=='#') 
            {
                d[x]=-1; continue;
            }
            if (j<n) a[x].push_back(x+1);
            if (i<m) a[x].push_back(x+n);
            if (s[j-1]>='0' && s[j-1]<='9') c[x]=s[j-1]-'0';
            else 
            {
                if (s[j-1]=='N' && i>1 && !d[x-n]) a[x].push_back(x-n); 
                if (s[j-1]=='W' && j>1 && !d[x-1]) a[x].push_back(x-1);
            }
        } 
        gets(t);
    }
    n*=m;
    for (int i=1;i<=n;i++)
        if (!d[i]) visit(i);
    for (int i=1;i<=n;i++)
      if (d[i]>0)
        for (int j=0;j<int(a[i].size());j++)
        {
            int y=a[i][j];
            if (d[y]<0) continue;
            if (d[i]!=d[y]) b[d[i]].push_back(d[y]);
        }
  if (d[1]<0) cout << 0 << endl;
  else calc(d[1]), cout << f[d[1]] << endl;
    return 0;
}

Code mẫu của ladpro98

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
const int M = 110;
const int N = M * M;
const int oo = INT_MAX;
using namespace std;
int n, m, cnt, timer, scc;
int low[N], num[N], lab[N], F[N], val[N], gain[N], ver[M][M];
bool was[N]; char ch[M][M];
vector<int> a[N], adj[N], super[N];

stack<int> S;
void Tarjan(int u) {
    num[u] = ++timer; low[u] = oo;
    S.push(u);
    FOR(i, 0, a[u].size()) {
        int v = a[u][i];
        if (was[v]) continue;
        if (num[v])
            low[u] = min(low[u], num[v]);
        else {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }
    if (low[u] >= num[u]) {
        int v;
        do {
            v = S.top();
            was[v] = true;
            lab[v] = scc; gain[scc] += val[v];
            super[scc].push_back(v);
            S.pop();
        } while (v != u);
        scc++;
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    REP(i, 1, m) REP(j, 1, n) ver[i][j] = ++cnt;
    REP(i, 1, m) REP(j, 1, n) cin >> ch[i][j];
    REP(i, 1, m) REP(j, 1, n) {
        if (ch[i][j] == '#') continue;
        if (ch[i][j + 1] != '#') a[ver[i][j]].push_back(ver[i][j + 1]);
        if (ch[i + 1][j] != '#') a[ver[i][j]].push_back(ver[i + 1][j]);
        if (ch[i][j] == 'W') {if (ch[i][j - 1] != '#') a[ver[i][j]].push_back(ver[i][j - 1]);} else
        if (ch[i][j] == 'N') {if (ch[i - 1][j] != '#') a[ver[i][j]].push_back(ver[i - 1][j]);} else
        val[ver[i][j]] = ch[i][j] - '0';
    }
    REP(i, 1, cnt) if (!was[i]) Tarjan(i);
    FOR(i, 0, scc) FOR(j, 0, super[i].size()) FOR(k, 0, a[super[i][j]].size())
        adj[i].push_back(lab[a[super[i][j]][k]]);
    FOR(i, 0, scc) {
        F[i] = gain[i];
        FOR(j, 0, adj[i].size())
        if (i != adj[i][j])
            F[i] = max(F[i], gain[i] + F[adj[i][j]]);
    }
    cout << F[lab[ver[1][1]]];
    return 0;
}

Code mẫu của RR

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

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 111;
const int MN2 = 111*111;

int m, n, now;
int low[MN][MN], num[MN][MN], reg[MN][MN], nReg;
int value[MN2], f[MN2], vao[MN2];
vector< pair<int,int> > ke[MN][MN];
vector<int> ke2[MN2];

pair<int,int> st[MN2];
int top;
char a[MN][MN];

void init() {
    FOR(i,1,m)
    FOR(j,1,n)
    if (a[i][j] != '#') {
        if (i < m && a[i+1][j] != '#') ke[i][j].PB(MP(i+1, j));
        if (j < n && a[i][j+1] != '#') ke[i][j].PB(MP(i, j+1));

        if (a[i][j] == 'W' && j > 1 && a[i][j-1] != '#') ke[i][j].PB(MP(i,j-1));
        if (a[i][j] == 'N' && i > 1 && a[i-1][j] != '#') ke[i][j].PB(MP(i-1,j));
    }
}

void add(int u, int v, int r) {
    reg[u][v] = r;
    if (a[u][v] >= '0' && a[u][v] <= '9') {
        value[r] += a[u][v] - '0';
    }
}

void dfs(int u, int v) {
    num[u][v] = ++now;
    low[u][v] = now;
    st[++top] = MP(u,v);

    REP(i,ke[u][v].size()) {
        int uu = ke[u][v][i].F, vv = ke[u][v][i].S;
        if (reg[uu][vv]) continue;

        if (num[uu][vv])
            low[u][v] = min(low[u][v], num[uu][vv]);
        else {
            dfs(uu, vv);
            low[u][v] = min(low[u][v], low[uu][vv]);
        }
    }

    if (low[u][v] == num[u][v]) {
        ++nReg;
        while (st[top] != MP(u,v)) {
            int uu = st[top].F, vv = st[top].S;
            add(uu, vv, nReg);
            --top;
        }
        add(u, v, nReg); --top;
    }
}

void build() {
    FOR(i,1,m) FOR(j,1,n) if (num[i][j] == 0 && a[i][j] != '#') {
        dfs(i,j);
    }

    // DEBUG(nReg);
    // PR(value, nReg);
    // FOR(i,1,m) {
    //     FOR(j,1,n) cout << reg[i][j] << ' ';
    //     cout << endl;
    // }

    FOR(u,1,m) FOR(v,1,n) {
        REP(i,ke[u][v].size()) {
            int uu = ke[u][v][i].F, vv = ke[u][v][i].S;
            int r1 = reg[u][v], r2 = reg[uu][vv];
            if (r1 != r2) {
                ke2[r1].PB(r2);
                vao[r2]++;
            }
        }
    }
}

int s[MN2], t, ls[MN2], cur;

void dp() {
    FOR(i,1,nReg)
    if (vao[i] == 0) {
        s[++t] = i;
    }
    while (t) {
        int u = s[t--];
        ls[++cur] = u;

        REP(i,ke2[u].size()) {
            int v = ke2[u][i];
            --vao[v];
            if (vao[v] == 0)
                s[++t] = v;
        }
    }

    FORD(t,cur,1) {
        int u = ls[t];
        f[u] = value[u];
        REP(i,ke2[u].size()) {
            int v = ke2[u][i];
            f[u] = max(f[u], f[v] + value[u]);
        }
    }

    // PR(f, nReg);

    cout << f[reg[1][1]] << endl;
}

int main() {
    scanf("%d%d\n", &m, &n);
    FOR(i,1,m) {
        scanf("%s\n", &a[i][1]);
    }
    init();
    build();
    dp();
    return 0;
}