As we all know, Max is the best video game player among her friends. Her friends were so jealous of hers, that they created an actual game just to prove that she’s not the best at games. The game is played on a directed acyclic graph (a DAG) with n vertices and m edges. There’s a character written on each edge, a lowercase English letter.
Max and Lucas are playing the game. Max goes first, then Lucas, then Max again and so on. Each player has a marble, initially located at some vertex. Each player in his/her turn should move his/her marble along some edge (a player can move the marble from vertex v to vertex u if there’s an outgoing edge from v to u). If the player moves his/her marble from vertex v to vertex u, the “character” of that round is the character written on the edge from v to u. There’s one additional rule; the ASCII code of character of round i should be greater than or equal to the ASCII code of character of round i - 1 (for i > 1). The rounds are numbered for both players together, i. e. Max goes in odd numbers, Lucas goes in even numbers. The player that can’t make a move loses the game. The marbles may be at the same vertex at the same time.
Since the game could take a while and Lucas and Max have to focus on finding Dart, they don’t have time to play. So they asked you, if they both play optimally, who wins the game?
You have to determine the winner of the game for all initial positions of the marbles.
Input
The first line of input contains two integers n and m (2 ≤ n ≤ 100, ).
The next m lines contain the edges. Each line contains two integers v, u and a lowercase English letter c, meaning there’s an edge from v to u written c on it (1 ≤ v, u ≤ n, v ≠ u). There’s at most one edge between any pair of vertices. It is guaranteed that the graph is acyclic.
Output
Print n lines, a string of length n in each one. The j-th character in i-th line should be ‘A’ if Max will win the game in case her marble is initially at vertex i and Lucas’s marble is initially at vertex j, and ‘B’ otherwise.
Examples
inputCopy
4 4
1 2 b
1 3 a
2 4 c
3 4 b
outputCopy
BAAA
ABAA
BBBA
BBBB
inputCopy
5 8
5 3 h
1 2 c
3 1 c
3 2 r
5 1 r
4 3 z
5 4 r
5 2 h
outputCopy
BABBB
BBBBB
AABBB
AAABA
AAAAB
两人在DAG中移动棋子，并且每个有向边有个字母代表权值，且每人的移动的边的权值必须比前一次大，当有一个人不能移动时，就输了；
问最后谁会赢；
思路：DAG中最长路，我们考虑DP( t,i,j ) 表示边为t时，先手为 i，后手为j 的博弈状态，那么下一个状态应该为 DP( t1,j,k ) ，其中t1>=t,k是i的下一步，
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 300005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int mp[300][300];
int dp[200][200][200];
int n, m;
int DP(char t, int i, int j) {
if (dp[t][i][j] >= 0)return dp[t][i][j];
for (int k = 1; k <= n; k++) {
if (t <= mp[i][k] && DP(mp[i][k], j, k) == 0)
return dp[t][i][j] = 1;
}
return dp[t][i][j] = 0;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
int i, j;
memset(mp, 0, sizeof(mp));
memset(dp, -1, sizeof(dp));
for (i = 0; i < m; i++) {
int u, v;
char ch[3];
cin >> u >> v;
cin >> ch;
mp[u][v] = ch[0];
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
DP('a', i, j);
}
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (dp['a'][i][j] % 2 == 1)cout << "A";
else cout << "B";
}
cout << endl;
}
}