P2474 [SCOI2008] Balance

You have $n$ weights, each of which is $1$ gram, $2$ grams, or $3$ grams. You do not know the exact mass of each weight, but you know some pairwise weight comparisons. You place two weights $A$ and $B$ on the left pan of a balance scale, and you need to choose two other weights to place on the right pan. How many unordered choices are there that make the left pan heavier ($c_1$), balance ($c_2$), or the right pan heavier ($c_3$)? (Only count choices for which the outcome is uniquely determined.) The choice is unordered; that is, choosing weights $1$ and $2$ is the same as choosing $2$ and $1$.

The first line contains three positive integers $n,A,B$ ($1\le A,B\le n,A\neq B$). The following $n$ lines contain the weight relation matrix. In row $i$, the $j$-th character is a plus `+` if weight $i$ is heavier than weight $j$, a minus `-` if weight $i$ is lighter than weight $j$, an equals `=` if weight $i$ and weight $j$ are equal, and a question mark `?` if their relation is unknown. It is guaranteed that there exists at least one configuration consistent with this matrix.

Output a single line containing three integers: $c_1,c_2,c_3$.

Constraints: $4\le n\le 50$. Translated by ChatGPT 5