本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-17 10:23:06

题目大意：在一个迷宫上从 $a$ 点到 $b$ 恰好走 $t$ 步的方案数有多少？ 数据范围: $n,m\leq100,t\leq15$

方法一，普通搜索

从终点出发，前起点方向走，如果能到起点就是一中方案。统计所有方案。得分 $48$, 超时。

#include <bits\/stdc++.h>
using namespace std;
int n, m, t, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[512][512];
void dfs(int x, int y, int tk) {
	if(tk == 0)	{ if(x == r1[0] && y == r1[1]) cnt++; return; }
	for(auto &fx : Fx)
	{
		int x_n = x + fx[0], y_n = y + fx[1];
		if(x_n < 1 || y_n < 1 || x_n > n || y_n > m || grid[x_n][y_n])
			continue;
		dfs(x_n, y_n, tk-1);
	}
}
int main() {
	cin >> n >> m >> t;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			char tmp; cin >> tmp;
			grid[i][j] = tmp == '*';
		}
	cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
	dfs(r2[0], r2[1], t);
	cout << cnt << endl;
	return 0;
}

方法二，考虑记忆化，步数总是从小到大的，如果前期已经处理过，直接拿来用即可。

设置记录步数的数组st，初始化为-1.设计起点的初值为1. 当一个点的四个方向处理完成后，这个点就没有必要再重复访问。 为什么初始设置为-1呢？这相当于访问标记。有的点路径数是0，如果初值为0，那么这些无效点可能会重复计算。

#include <bits\/stdc++.h>
using namespace std;
int n, m, t, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[512][512];
int st[112][112][20];
int dfs(int x, int y, int tk) {
	if(st[x][y][tk] !=-1)return st[x][y][tk];
	if(tk == -1)	{  return 0; }
	if(abs(r1[0]-x)+abs(r1[1]-y)>tk)return 0;\/\/可行性剪枝。 
	int tmp=0;
	for(auto &fx : Fx)
	{
		int x_n = x + fx[0], y_n = y + fx[1];
		if(x_n < 1 || y_n < 1 || x_n > n || y_n > m || grid[x_n][y_n])
			continue;		
		tmp+=dfs(x_n, y_n, tk-1);		
	}
	return st[x][y][tk]=tmp;
}
int main() {
	cin >> n >> m >> t;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			char tmp; cin >> tmp;
			grid[i][j] = tmp == '*';
		}
	cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
	memset(st,-1,sizeof(st));
	st[r1[0]][r1[1]][0]=1;
	dfs(r2[0], r2[1], t);
	cout << st[r2[0]][r2[1]][t] << endl;
	return 0;
}

方法4 DFS能写，bfs也一样可以写。

在处理入队的过程中，一个点可能从多个方向处理几次，但只需要入队一次，可以通过访问标记或者st的数值来标记入队情况，避免重复入队。

bfs总是中按照0，1，2这样的顺利来处理的。

#include <bits\/stdc++.h>
using namespace std;
int n, m, k, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[112][112],vis[112][112][20];
int st[112][112][20];
struct node{
	int x,y,st;
};
queue<node>q;
void bfs(){
	q.push({r1[0],r1[1],0});	
	st[r1[0]][r1[1]][0]=1;
	vis[r1[0]][r1[1]][0]=1;
	while(q.size()){
		node t=q.front();		
		q.pop();
		if(t.st==k) continue;
		for(int i=0;i<4;i++){
			int tx=t.x+Fx[i][0],ty=t.y+Fx[i][1],ts=t.st+1;
			if(tx>n||ty>m||tx<1||ty<1||grid[tx][ty])continue;			
			st[tx][ty][ts]+=st[t.x][t.y][t.st];
			if(!vis[tx][ty][ts])q.push({tx,ty,ts}),vis[tx][ty][ts]=1;	
		}		
	}	
}
int main() {
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			char tmp; cin >> tmp;
			grid[i][j] = tmp == '*';
		}
	cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
	bfs();
	cout << st[r2[0]][r2[1]][k] << endl;
	return 0;
}

方法四 动态规划

能用记忆化搜索来完成的题目基本可以动态规划。动态规划的特点是无后效性，本题只要通过步数来划分阶段，虽然结点间相互可达，但也有了先后关系。

设计状态为 $st[i][j][l]$ 表示达到$(i,j)$用了 $l$ 步的方案数。以步数为阶段扩展即可。

\/\/DP写法 
#include <bits\/stdc++.h>
using namespace std;
int n, m, t, r1[2], r2[2], cnt = 0;
int Fx[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
bool grid[512][512];
int st[112][112][20];

int main() {
	cin >> n >> m >> t;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			char tmp;
			cin >> tmp;
			grid[i][j] = tmp == '*';
		}
	cin >> r1[0] >> r1[1] >> r2[0] >> r2[1];
\/\/	memset(st,-1,sizeof(st));
	st[r1[0]][r1[1]][0]=1;
	for(int l=1; l<=t; l++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) {
				for(auto &fx : Fx) {
					int x_n = i + fx[0], y_n = j + fx[1];
					if(x_n < 1 || y_n < 1 || x_n > n || y_n > m || grid[x_n][y_n]||!st[x_n][y_n][l-1])
						continue;
					st[i][j][l]+=st[x_n][y_n][l-1];
				}

			}

	cout << st[r2[0]][r2[1]][t] << endl;
	return 0;
}
\/*
10 10 7
**........
..**......
*.........
.*.*....*.
..........
..*.**....
..........
.**..*....
......**..
...***....
5 4 7 3
*\/