【Codeforces Round #459 (Div. 2) D】MADMAX

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

const int N = 100;

int n,m;
vector <pair<int,int> > g[N+10];
int f[N+10][N+10][26+2][2+2];

int dfs(int x,int y,int now,int turn){
    if (f[x][y][now][turn]!=-1) return f[x][y][now][turn];
    if (turn == 0){
        for (auto temp:g[x]){
            if (temp.second>=now){
                if (dfs(temp.first,y,temp.second,1-turn)==0){
                    return f[x][y][now][turn] = 0;
                }
            }
        }
        return f[x][y][now][turn] = 1;
    }else{
        for (auto temp:g[y]){
            if (temp.second>=now){
                if (dfs(x,temp.first,temp.second,1-turn)==1){
                    return f[x][y][now][turn] = 1;
                }
            }
        }
        return f[x][y][now][turn] = 0;
    }
}

int main(){
    #ifdef LOCAL_DEFINE
        freopen("rush_in.txt", "r", stdin);
    #endif
    ios::sync_with_stdio(0),cin.tie(0);
    memset(f,255,sizeof f);
    cin >> n >> m;
    for (int i = 1;i <= m;i++){
        int x,y;char s[3];
        cin >> x >> y >> s;
        g[x].push_back(make_pair(y,s[0]-'a'));
    }
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            if (dfs(i,j,0,0)==1)
                cout<<'B';
            else
                cout<<'A';
        }
        cout<<endl;
    }
    return 0;
}