首页 > 代码库 > BNUOJ 1055 走迷宫2
BNUOJ 1055 走迷宫2
走迷宫2
1000ms
65535KB
64-bit integer IO format: %lld Java class name: Main
走迷宫是很有趣的一种游戏,能够锻炼人的记忆力和思维.现在,HK被困在一个迷宫里面了,请你帮助他计算一下有多少种不同的走法,能够让他走出迷宫.这个迷宫很奇怪,HK只能够沿着向上或者向右的方向走,不能回头.
迷宫使用一个N*M的矩阵来描述,矩阵中用‘.‘代表空格可以通行,用‘*‘代表障碍物,用‘S‘代表出发点,用‘T‘代表出口.例如下面的一个矩阵就描述了一个8*8的迷宫
.....T..
..*****.
......*.
*.***.*.
......*.
.****.*.
S..*....
........
View Code
迷宫使用一个N*M的矩阵来描述,矩阵中用‘.‘代表空格可以通行,用‘*‘代表障碍物,用‘S‘代表出发点,用‘T‘代表出口.例如下面的一个矩阵就描述了一个8*8的迷宫
.....T..
..*****.
......*.
*.***.*.
......*.
.****.*.
S..*....
........
Input
每个输入文件只包含一组输入数据.
每组数据第一行是两个正整数N和M(N,M<=100).
接着是一个N*M的矩阵.
每组数据第一行是两个正整数N和M(N,M<=100).
接着是一个N*M的矩阵.
Output
输出HK能够选用的不同方法数(由于结果可能很大,输出模1908的余数即可).
Sample Input
8 8.....T....*****.......*.*.***.*.......*..****.*.S..*............
Sample Output
1
Source
第七届北京师范大学程序设计竞赛热身赛第五场
Author
HK@Sphinx
解题:老是搞不懂dp啊!!!!!!!!!!!!!哎,学渣没救了!为什么要逆着呢!因为只能向上或者向右,逆着存,就能向下或者向右走了!
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <vector> 6 #include <climits> 7 #include <algorithm> 8 #include <cmath> 9 #define LL long long10 using namespace std;11 char table[110][110];12 int dp[110][110];13 int main() {14 int rows,cols,x1,x2,y1,y2,i,j;15 bool flag;16 while(~scanf("%d %d",&rows,&cols)){17 getchar();18 for(i = rows; i; i--){19 for(j = 1; j <= cols; j++){20 table[i][j] = getchar();21 if(table[i][j] == ‘S‘){22 x1 = i;y1 = j;23 }else if(table[i][j] == ‘T‘){24 x2 = i;y2 = j;25 }26 }27 getchar();28 }29 memset(dp,0,sizeof(dp));30 dp[x1][y1] = 1;31 table[x1][y1] = ‘*‘;32 flag = false;33 for(i = x1; i <= rows; i++){34 for(j = y1; j <= cols; j++){35 if(table[i][j] != ‘*‘){36 dp[i][j] = dp[i][j-1] + dp[i-1][j];37 if(table[i][j] == ‘T‘){38 flag = true;break;39 }40 }41 }42 if(flag) break;43 }44 printf("%d\n",flag?dp[x2][y2]%1908:0);45 }46 return 0;47 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。