题意

有多少条路能刚好用 $t$ 秒从起点到终点？

PS：能走走过的路

思路

由于可以走走过的路，所以不用标记数组。

每个点都可以从四周来，所以这个点的方案数是从上一秒的四周的点的方案数加起来的和（f[i][j][t] += f[xi][yi][t - 1]）

代码

#include <bits/stdc++.h>
using namespace std;
bool a[105][105];
int f[105][105][20],dx[] = {-1,1,0,0},dy[] = {0,0,-1,1},sx,sy,ex,ey;
int main(int argc, char **argv){
	int n,m,t;
	cin >> n >> m >> t;
	for (int i = 1;i <= n;i++){
		string s;
		cin >> s;
		for (int j = 1;j <= m;j++){
			if (s[j - 1] == '.')	a[i][j] = 1;	// 能走的地方
		}
	}
	cin >> sx >> sy >> ex >> ey;

	f[sx][sy][0] = 1;
	for (int k = 1;k <= t;k++){	// 每一秒（阶段）
		// 遍历地图
		for (int i = 1;i <= n;i++){
			for (int j = 1;j <= m;j++){
				for (int x = 0;x < 4;x++){	// 遍历四周
					int xi = i + dx[x],yi = j + dy[x];
					if (a[xi][yi])	f[i][j][k] += f[xi][yi][k - 1];
				}
			}
		}
	}
	cout << f[ex][ey][t];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
char a[114][114];
int sx,sy,ex,ey;
int xl[4]={0,0,1,-1};
int yl[4]={1,-1,0,0};
int f[114][114][16];
int dfs(int x,int y,int c)
{
	if(f[x][y][c]!=-1)
	{
		return f[x][y][c];
	}
	if(c>t)
	{
		return f[x][y][c]=0;
	}
	if(abs(x-ex)+abs(y-ey)>t-c)//这是一个重要的剪枝
	{
		return f[x][y][c]=0;
	}
	if(c==t)
	{
		if(x==ex && y==ey)//终点
		{
			return f[x][y][c]=1;
		}
		else
		{
			return f[x][y][c]=0;
		}
	}
	int ti=0;
	for(int i=0;i<4;i++)//4个方向
	{
		int xs=x+xl[i],ys=y+yl[i];
		if(xs>=1 && xs<=n && ys>=1 && ys<=m && a[xs][ys]=='.')
		{
			ti+=dfs(xs,ys,c+1);
		}
	}
	return f[x][y][c]=ti;
}
int main()
{
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>sx>>sy>>ex>>ey;
	memset(f,-1,sizeof(f));//初始化
	cout<<dfs(sx,sy,0);//输出
	return 0;//完结散花
}

不要点差评,我与黄旻哲的方法不一样

思路

DFS(黄旻哲是DP)

用一个$f$的3维数组,存储每个点的步数

有个点要剪枝

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
char a[114][114];
int sx,sy,ex,ey;
int xl[4]={0,0,1,-1};
int yl[4]={1,-1,0,0};
int f[114][114][16];
int dfs(int x,int y,int c)
{
	if(f[x][y][c]!=-1)
	{
		return f[x][y][c];
	}
	if(c>t)
	{
		return f[x][y][c]=0;
	}
	if(abs(x-ex)+abs(y-ey)>t-c)//这是一个重要的剪枝
	{
		return f[x][y][c]=0;
	}
	if(c==t)
	{
		if(x==ex && y==ey)//终点
		{
			return f[x][y][c]=1;
		}
		else
		{
			return f[x][y][c]=0;
		}
	}
	int ti=0;
	for(int i=0;i<4;i++)//4个方向
	{
		int xs=x+xl[i],ys=y+yl[i];
		if(xs>=1 && xs<=n && ys>=1 && ys<=m && a[xs][ys]=='.')
		{
			ti+=dfs(xs,ys,c+1);
		}
	}
	return f[x][y][c]=ti;
}
int main()
{
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>sx>>sy>>ex>>ey;
	memset(f,-1,sizeof(f));//初始化
	cout<<dfs(sx,sy,0);//输出
	return 0;//完结散花
}

不要点差评,我与黄旻哲的方法不一样

思路

DFS(黄旻哲是DP)

用一个$f$的3维数组,存储每个点的步数

有个点要剪枝

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,t;
char a[114][114];
int sx,sy,ex,ey;
int xl[4]={0,0,1,-1};
int yl[4]={1,-1,0,0};
int f[114][114][16];
int dfs(int x,int y,int c)
{
	if(f[x][y][c]!=-1)
	{
		return f[x][y][c];
	}
	if(c>t)
	{
		return f[x][y][c]=0;
	}
	if(abs(x-ex)+abs(y-ey)>t-c)//这是一个重要的剪枝
	{
		return f[x][y][c]=0;
	}
	if(c==t)
	{
		if(x==ex && y==ey)//终点
		{
			return f[x][y][c]=1;
		}
		else
		{
			return f[x][y][c]=0;
		}
	}
	int ti=0;
	for(int i=0;i<4;i++)//4个方向
	{
		int xs=x+xl[i],ys=y+yl[i];
		if(xs>=1 && xs<=n && ys>=1 && ys<=m && a[xs][ys]=='.')
		{
			ti+=dfs(xs,ys,c+1);
		}
	}
	return f[x][y][c]=ti;
}
int main()
{
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>sx>>sy>>ex>>ey;
	memset(f,-1,sizeof(f));//初始化
	cout<<dfs(sx,sy,0);//输出
	return 0;//完结散花
}