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

淩亂°似流年 2022-12-11 13:53 161阅读 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 条评论，161人围观）

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

相关阅读

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

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

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

相关递推与递归

递推 include <stdio.h> include <stdlib.h> int main(int argc, char argv[])

忘是亡心i/ 2022年12月12日 04:55/ 0 赞/ 203 阅读

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

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

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

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

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

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

相关算法基础之递推

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

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

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

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

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

相关 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 赞/ 178 阅读

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

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

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

相关【数据结构与算法 8】递归之迷宫问题

一、简介递归就是方法自己调用自己，每次调用时传入不同的参数，递归有利于编程者解决复杂的问题，同时可以让代码变得简洁。二、用一个例子引出递归概念 pub

旧城等待，/ 2021年08月29日 12:09/ 0 赞/ 407 阅读

相关递归解决迷宫问题

一迷宫功能 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

╰+哭是因爲堅強的太久メ/ 2021年07月24日 11:58/ 0 赞/ 435 阅读