Dotcpp  >  编程题库  >  蓝桥杯2015年第六届真题-生成树计数
题目 1839:

蓝桥杯2015年第六届真题-生成树计数

时间限制: 5s 内存限制: 192MB 提交: 149 解决: 42

题目描述

给定一个 n*m 的格点图,包含 n 行 m 列共 n*m 个顶点,相邻的顶点之间有一条边。
【图1.png】给出了一个3*4的格点图的例子。


如果在图中删除部分顶点和其相邻的边,如上图删除第2行第3列和第3行第1列的顶点后,如【图2.png】所示。


图的生成树指包含图中的所有顶点和其中的一部分边,使得任意两个顶点之间都有由边构成的唯一路径。如果两个生成树包含有不同的边即被认为不同,则上图中共有31种不同的生成树,其中a边不选有10种,a边选有21种。
给出格点图中保留的顶点的信息,请计算该图一共有多少种不同的生成树。

输入格式

输入的第一行包含两个整数n, m,用空格分隔,表示格点图的行数和列数。
接下来n行,每行m个字母(中间没有分隔字符),每个字母必然是大写E或大写N,E表示对应的顶点存在,N表示对应的顶点不存在。保证存在至少一个顶点。

输出格式

输出一行,包含一个整数,表示生成树的个数。答案可能很大,你只需要计算答案除以1000000007的余数即可。

样例输入

3 4
EEEE
EENE
NEEE

样例输出

31

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签