学步园

走迷宫是很有趣的一种游戏,能够锻炼人的记忆力和思维.现在,HK被困在一个迷宫里面了,请你帮助他计算一下有多少种不同的走法,能够让他走出迷宫.这个迷宫很奇怪,HK只能够沿着向上或者向右的方向走,不能回头.


迷宫使用一个N*M的矩阵来描述,矩阵中用'.'代表空格可以通行,用'*'代表障碍物,用'S'代表出发点,用'T'代表出口.例如下面的一个矩阵就描述了一个8*8的迷宫



.....T..

..*****.

......*.

*.***.*.

......*.

.****.*.

S..*....

........

每个输入文件只包含一组输入数据.

每组数据第一行是两个正整数N和M(N,M<=100).

接着是一个N*M的矩阵.

输出HK能够选用的不同方法数(由于结果可能很大,输出模1908的余数即可).

8 8
.....T..
..*****.
......*.
*.***.*.
......*.
.****.*.
S..*....
........

1

#include<stdio.h>

const int mod = 1908;

char map[103][103];
int dp[103][103];

int n,m;

int res(){
	int i,j,si,sj;
	for(i=n;i>0;i--){
		scanf("%s",map[i]+1);
		for(j=1;j<=m;j++){
			if(map[i][j]=='S')
				si=i,sj=j;
			dp[i][j]=0;
		}
	}
	dp[si][sj]=1;
	map[si][sj]='*';
	for(i=si;i<=n;i++){ // DP   dp[i][j]=dp[i-1][j]+dp[i][j-1]
		for(j=sj;j<=m;j++)
			if(map[i][j]!='*'){
				dp[i][j]=dp[i-1][j]+dp[i][j-1];
				if(map[i][j]=='T') return dp[i][j];
			}
	}
	return 0;
}

int main(){ // 简单DP，容易误导为 BFS搜索 
	scanf("%d%d",&n,&m);
	printf("%d\n",res()%mod);
	return 0;
}