BZPRO
#3515. EvenPaths
内存限制：256 MiB
时间限制：2 Sec
提交
提交记录
讨论
题目描述
有一个迷宫，迷宫由房间和单向的走廊组成。每条走廊都是从一个房间单向走向另一个房间。房间编号为0到N-1。迷宫有一个性质，对于每个房间，一旦通过走廊离开房间，则无法再回到这个房间。
每个房间可能或者不可能包含一个障碍物。有障碍物的房间则无法通过。
如果有K个房间可能包含障碍物，则整个迷宫有2^K种状态。问在这些状态中，有多少种状态，从0号房间到1号房间有偶数条路径。
输入格式
第一行一个整数N。
第二行一个长度为N的字符串，第i个字符为-或?。-表示第i-1个房间不含有障碍物，?表示第i-1个房间可能含有障碍物。
第三行至结束是一个邻接矩阵，第i行第j列为Y则表示房间i到j有一条单向走廊。
输出格式
一个整数，如题目中描述。
样例
样例输入
5
--???
NYYNN
NNNNY
NYNNN
YNNNN
NNNNN
样例输出
4
数据范围与提示
对于100%的数据，1<=N<=50，邻接矩阵中最多有500个Y，?最多有32个，0号和1号房间不会有可能有障碍物。
BZPRO