基础算法题——迷宫（递推）

淩亂°似流年 2022-12-11 13:53 175阅读 0赞

### 迷宫 ###

[题目链接][Link 1]  
![题目1][1]  
![题目2][2]

--------------------

#### 解题思路 ####

##### ①、暴力法 #####

利用 dfs 遍历每一条可能的路径，将遍历的权值和不断取余。  
不足：当 n、m 取较大的情况下，所遍历的路径可能会暴增，出现超时的情况。

--------------------

##### ②、递推法 #####

从题目上我们可以发现，最终的权值和是要对 mod 取余的，利用这个特点，我们可以实现递推。

**状态转移方程：  
dp\[i\]\[j\]\[k\] | = dp\[i-1\]\[j\]\[(k-mg\[i\]\[j\]+mod)%mod\];  
dp\[i\]\[j\]\[k\] | = dp\[i\]\[j-1\]\[(k-mg\[i\]\[j\]+mod)%mod\];**

原理：在迷宫上，假设已知点(i-1, j)与(i, j-1)所能得到的权值和，那么我们就能求出点(i, j)所能得到的权力和。

--------------------

#### AC代码 ####

#include<bits/stdc++.h>
    const int mod = 1e4+7;
    bool dp[110][110][10010];
    int mg[110][110], ans=0; 
    
    int main(){ 
    	int n, m;
    	memset(dp, false, sizeof(dp));
    	memset(mg, 0, sizeof(mg));
    	scanf("%d%d", &n, &m);
    	
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=m; j++){ 
    		int tmp;
    		scanf("%d", &tmp);
    		mg[i][j]=tmp%mod;
    	}
    	
    	dp[1][1][mg[1][1]] = true;
    	for(int i=1; i<=n; i++)
    	for(int j=1; j<=m; j++)
    	for(int k=0; k<mod; k++){ 
    		dp[i][j][k] |= dp[i-1][j][(k-mg[i][j]+mod)%mod];
    		dp[i][j][k] |= dp[i][j-1][(k-mg[i][j]+mod)%mod]; 
    	}
    	for(int i=0; i<mod; i++)
    	if(dp[n][m][i]) ans++;
    	printf("%d", ans);
    	
    	return 0;
    }

[Link 1]: https://ac.nowcoder.com/acm/contest/7412/I
[1]: /images/20221123/8a37e12f05894d81970d4df8f73f6de6.png
[2]: /images/20221123/1c5460ced9c04844bd2aa788229daae8.png

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法题】机器人走迷宫

机器人走迷宫 [力扣62. 不同路径][62.] ![在这里插入图片描述][947a506a842242e08c4b47b8db227647.png] pa

约定不等于承诺〃/ 2024年03月27日 11:00/ 0 赞/ 85 阅读

相关算法——动态规划（DP）——递推

一、DP > 动态规划是一种解决多阶段决策过程中最优化问题的数学方法。其关键思想是将复杂问题分解成简单的子问题，并利用已知的子问题的解来构建原始问题的解，从而避免重

我不是女神ヾ/ 2024年02月05日 15:56/ 0 赞/ 2 阅读

相关一起学算法（递推篇）

前言：递推最通俗的理解就是数列，递推和数列的关系就好比算法和数据结构的关系，数列有点像数据结构中的顺序表，而递推就是一个循环或者迭代的过程的枚举过程 1.斐波那契数列

雨点打透心脏的1/2处/ 2023年10月14日 10:13/ 0 赞/ 23 阅读

相关递归--迷宫问题

1 需求如下图： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

古城微笑少年丶/ 2023年05月22日 13:24/ 0 赞/ 30 阅读

相关基础算法题——迷宫（递推）

迷宫 [题目链接][Link 1] ![题目1][1] ![题目2][2] -------------------- 解题思路 ①、暴力法利用

淩亂°似流年/ 2022年12月11日 13:53/ 0 赞/ 176 阅读

相关 c语言用递归算法实现迷宫,[原创]递归随机迷宫生成算法详解

该楼层疑似违规已被系统折叠隐藏此楼查看此楼 \include \includ

分手后的思念是犯贱/ 2022年10月16日 06:04/ 0 赞/ 227 阅读

相关算法基础之递推

算法基础之递推（C++示例）所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题

绝地灬酷狼/ 2022年09月08日 00:19/ 0 赞/ 169 阅读

相关算法笔记动态规划递推写法

1. 什么是动态规划动态规划是一种用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问

蔚落/ 2022年06月01日 08:28/ 0 赞/ 237 阅读

相关 Fibonacci序列递归算法与递推（Java）

Fibonacci递推公式： f(1) = f(2) = 1;f(n) = f(n-1)+f(n-2)(n>2).在这里取他除以10007的余数递归 pub

不念不忘少年蓝@/ 2022年04月17日 01:53/ 0 赞/ 201 阅读

相关递推（二）：递推法的应用

下面通过一些典型实例及其扩展来讨论递推法的应用。【例2】骨牌铺方格在2×n的一个长方形方格中，用一种2×1的骨牌铺满方格。输入n（n<=40），

青旅半醒/ 2021年11月24日 00:22/ 0 赞/ 365 阅读