首页 > 代码库 > BNUOJ 1055 走迷宫2

BNUOJ 1055 走迷宫2

2024-07-11 04:14:35   220人阅读

走迷宫2

1000ms
65535KB
 
64-bit integer IO format: %lld      Java class name: Main
 
走迷宫是很有趣的一种游戏,能够锻炼人的记忆力和思维.现在,HK被困在一个迷宫里面了,请你帮助他计算一下有多少种不同的走法,能够让他走出迷宫.这个迷宫很奇怪,HK只能够沿着向上或者向右的方向走,不能回头.

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


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

Input

每个输入文件只包含一组输入数据.
每组数据第一行是两个正整数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 }
View Code

 


联系
我们