走迷宫 港控/mmm° 2022-07-12 07:05 205阅读 0赞 think: 1题目似乎没有很明显的模板性,我是否应该反思转换学习图的方法,自己目前的认识水平这个题目很难找到DFS与BFS的影子,自己应该把思维延伸,将DFS与BFS的思想运用到解题中,而不是急于求成,越是急于求成,根基越是不牢,最后只会导致自己寸步难行,既然自己在学习图的存储结构中决定展现自己的做题风格,那么自己越是艰难越不能盲目做题, 题目说每次可以往上下左右四个方向移动也就意味着每在一个有效位置最多可有4种选择方案,从一个点移动到另一个点是否意味着更适合深度优先搜索,而对于从一个点回到这个点,是否意味着更适合广度优先搜索,深度优先搜索的思想是否又与递归思想有着千丝万缕的关系呢?为广度优先搜索的思想是否又与队列思想有着千丝万缕的关系呢?不断摸索,更要不断反思总结,只有这样才能进步 [sdut原题链接][sdut] 走迷宫 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 一个由n \* m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是不能走动,求从起点到终点经过每个格子至多一次的走法数。 Input 第一行一个整数T 表示有T 组测试数据。(T <= 110) 对于每组测试数据: 第一行两个整数n, m,表示迷宫有n \* m 个格子。(1 <= n, m <= 6, (n, m) !=(1, 1) ) 接下来n 行,每行m 个数。其中第i 行第j 个数是0 表示第i 行第j 个格子可以走,否则是1 表示这个格子不能走,输入保证起点和终点都是都是可以走的。 任意两组测试数据间用一个空行分开。 Output 对于每组测试数据,输出一个整数R,表示有R 种走法。 Example Input 3 2 2 0 1 0 0 2 2 0 1 1 0 2 3 0 0 0 0 0 0 Example Output 1 0 4 Hint Author 以下为accepted代码 #include <stdio.h> #include <string.h> int a[9][9], visit[9][9]; int n, m, flag; void ans(int fn, int fm) { int i, tn, tm; int jn[] = {0, 0, -1, 1}; int jm[] = {-1, 1, 0, 0}; for(i = 0; i < 4; i++) { tn = fn + jn[i]; tm = fm + jm[i]; if(tn == n && tm == m) flag++; else if(tn >= 1 && tn <= n && tm >= 1 && tm <= m) { if(a[tn][tm] == 1 && visit[tn][tm] == 0) { visit[tn][tm] = 1; ans(tn, tm); //visit[tn][tm] = 0; } } } visit[fn][fm] = 0; } int main() { int T, i, j, x; scanf("%d", &T); while(T--) { flag = 0; memset(a, 0, sizeof(a)); memset(visit, 0, sizeof(visit)); scanf("%d %d", &n, &m); for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { scanf("%d", &x); if(x == 0) a[i][j] = 1; else a[i][j] = 0; } } visit[1][1] = 1; ans(1, 1); printf("%d\n", flag); } return 0; } /*************************************************** User name: Result: Accepted Take time: 520ms Take Memory: 116KB Submit time: 2017-02-15 18:22:18 ****************************************************/ [sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2012/pid/2449
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory limit: 65536K 题目描述 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终 向右看齐/ 2022年09月25日 11:21/ 0 赞/ 209 阅读
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory limit: 65536K 题目描述 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终 喜欢ヅ旅行/ 2022年09月25日 11:20/ 0 赞/ 185 阅读
相关 走迷宫 Problem Description 有一个m\n格的迷宫(表示有m行、n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,输入这m\n个数据和起始点、结 分手后的思念是犯贱/ 2022年07月13日 13:40/ 0 赞/ 190 阅读
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 超、凢脫俗/ 2022年07月12日 13:10/ 0 赞/ 196 阅读
相关 走迷宫 Problem Description 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是 深藏阁楼爱情的钟/ 2022年07月12日 07:14/ 0 赞/ 218 阅读
相关 走迷宫 Problem Description 一个由n \ m 个格子组成的迷宫,起点是(1, 1), 终点是(n, m),每次可以向上下左右四个方向任意走一步,并且有些格子是 我不是女神ヾ/ 2022年07月12日 07:14/ 0 赞/ 190 阅读
相关 走迷宫 think: 1题目似乎没有很明显的模板性,我是否应该反思转换学习图的方法,自己目前的认识水平这个题目很难找到DFS与BFS的影子,自己应该把思维延伸,将DFS与BFS的思 港控/mmm°/ 2022年07月12日 07:05/ 0 赞/ 206 阅读
相关 走迷宫 通过栈将每次可以通过的路径保存起来。 但是要注意关于入口点和出口点的一些边界问题 一不小心就可能因为边界问题陷入死循环或者程序直接崩溃。 pragma war 傷城~/ 2022年06月17日 07:12/ 0 赞/ 188 阅读
相关 走迷宫 走迷宫 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description 秒速五厘米/ 2022年06月10日 12:25/ 0 赞/ 191 阅读
相关 走迷宫问题 问题描述: 给一迷宫表个和入口位置,找出并打印出从入口到出口的路径 注意:迷宫表格我们可以用一个二维数组来表示,但是如果用二维数组表示,将唯一固定,迷宫趣味性大大降低并 朱雀/ 2022年05月31日 05:30/ 0 赞/ 252 阅读
还没有评论,来说两句吧...