NC21353. 路径计数

描述

输入描述

第一行输入一个整数N (2 ≤ N ≤ 50)
接下来N行每行N个字符表示图的邻接矩阵g
g[i][j]='Y'表示ij可达
g[i][j]='N'表示ij不可达

输出描述

输出一个整数

示例1

输入:

3
NYN
YNY
NNN

输出:

2

说明:

第一条路径为
0 -> 1 -> 2 （走了0->1 1->2）
第二条路径为
0 -> 1 -> 0 -> 1 -> 2 （1->0是新的走法）
如果先走第二条路径，第一条路径就不能再走

示例2

输入:

3
NNY
YNY
YNN

输出:

2

示例3

输入:

2 
NN
NN

输出:

0

示例4

输入:

4
NYYY
NNNY
NNNY
NNNN

输出:

3

原站题解