1703: [NewOJ Contest 1] 地图

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:114 通过:38

题目描述

在一个n*n的地图上,小蓝在左上角(1,1),他要去往右下角(n,n)。
小蓝每次可以往右走或者往下走,而且他最多只能改变3次方向。
地图中部分位置存在障碍物“*”,小蓝无法经过存在障碍物的位置。
地图中“S”表示小蓝的位置,在(1,1)处,“T”表示终点位置,在(n,n)处;“*”表示障碍物;“.”表示空地。

例如:

S..
.*.
..T

小蓝有两种方案:DDRR、RRDD(其中R表示向右走,D表示向下走),均为1次拐弯。

再例如:

S..
...
..T

小蓝有六种方案:

1次拐弯:DDRR、RRDD;

2次拐弯:DRRD、RDDR;

3次拐弯:DRDR、RDRD。
现在给定一张50*50的地图,求小蓝走到终点的方案数。

输入格式

由于本题为固定答案,无输入,只需输出1个数字表示答案,不要输出其他任何字符。

输入样例 复制

..................................................
..................................................
...*..............................................
...........*......*...............................
..............................*...................
.............................................*....
.*......................................*.........
..................................................
..................................................
..................................................
..................................................
.........................................*........
.......*......*...................................
..................................................
................................................*.
..................................................
..........................*........*..............
.................................................*
................................*............*....
............*...........*.........................
*.................................................
................*.....................*...........
.................................*................
..............*.....................*....*........
..................................................
..................................................
.......................*..........................
......*.............................*.............
........*.........................................
.......................*....*............*........
..................................................
........*..................*......................
..................................................
...............*..................................
*...*.............................................
............................................*.....
..................................................
.........*............................*...........
......*...........................................
........*.........................................
.............................*............*.......
....*......*.....*................................
................................*.................
................................................*.
.......................................*..........
..........................................*.......
.....*............................................
..........................*.................*.....
..................................................
..................................................

输出样例 复制