CF589E Training with Doors
题目描述
上校将为下士进行训练。上校有一个房间，里面有无数扇紧闭的门，一扇接一扇地排成一行。上校能够执行以下两个命令：
1.打开第一扇关着的门，走到下一扇关着门的前面（将此命令标记为“（”）
2.走到当前打开的最后一扇门的前面并将其关闭（将此命令标记为“）”）。
如果满足以下条件，则命令序列有效：
1.当应该执行命令“）”时，至少有一扇门是打开的（第一个命令不应该是“）”）
2.执行完序列中的所有命令后，所有门都关闭了（船长站在第一扇门前）。
上校收到了一个字符网格——一个有n行和m列的网格，其中每个元素包含一个命令，即“（”或“）”。上校必须为上尉选择一个训练计划——从字符网格中选择一个矩形X。如果所选矩形X的每一行都是有效的命令序列，则训练计划有效。
你需要给出有多少满足的矩形X。所选的矩形X应该是完整的的(即中间没有空格)。即使所包含的命令相同，如果它们的位置不同，那也算不同的矩形。
输入格式
第一行包含两个整数n和m(1
输出格式
有多少不同的方法数(不同的，满足条件的矩形)
翻译:WAITER