P16074

天平

难度 6 级 小学 数据结构入门 最短路 差分约束
讨论 统计 3通过 13提交 23.1%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

你有 n 个砝码,均为 1 克,2 克或者 3 克。你并不清楚每个砝码的重量,但你知道其中一些砝码重量的大小关系。你把其中两个砝码 A 和 B 放在天平的左边,需要另外选出两个砝码放在天平的右边。问:有多少种选法(选法是无序的,也就是说选择砝码 1 和 2 或者 2 和 1 是一种选法)使得天平的左边重(c_1)、一样重(c_2)、右边重(c_3)?(只有结果保证唯一确定的选法才统计在内)

输入

第一行包含三个正整数 n,A,B(1\le A,B\le n,A\neq B)。

以下 n 行包含重量关系矩阵,其中第 i 行第 j 个字符为加号 + 表示砝码 i 比砝码 j 重,减号 - 表示砝码 i 比砝码 j 轻,等号 = 表示砝码 i 和砝码 j 一样重,问号 ? 表示二者的关系未知。

数据保证至少存在一种情况符合该矩阵。

输出

仅一行,包含三个整数,即 c_1,c_2,c_3。

样例

样例 1
输入
6 2 5
?+????
-?+???
?-????
????+?
???-?+
????-?
输出
1 4 1
样例 2
输入
14 8 4
?+???++?????++
-??=?=???????=
??????????=???
?=??+?==??????
???-???-???-??
-=????????????
-??=???=?-+???
???=+?=???????
??????????????
??????+???????
??=???-????-??
????+?????+???
-?????????????
-=????????????
输出
18 12 11

提示

4\le n\le 50。

来源

四川省选

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交