善良先生

用户名：Officialmomo

访问量：23528

签　名：

此时已莺飞草长，爱的人正在路上

等　　级
排　　名	167
经　　验	7061
参赛次数	8
文章发表	42
年　　龄	0
在职情况	学生
学　　校	东莞理工学院
专　　业	计算机科学与技术

　　自我简介：

穿越人海只为与你相拥

TA的其他文章

双向链表的创建以及基本功能的实现
浏览：970

函数重载及带默认参数的函数
浏览：572

C++中auto,static,register,extern四种关键字的作用
浏览：635

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

40.殊途同归-题解(C++代码)

　　作者: 善良先生　　　　发表时间：2019-12-13 14:55:58 浏览：600　|　评论：0　

原题链接：殊途同归

这个题确实花了一天的时间，开始用BFS的做法，，但是只能做出一种方案的最短路径长度。。。
随后在大佬的建议下用DFS完成了这道题，，期间也多次请教大佬，最后终于完成。。

问题难的地方就在于如何求出它的方案数。
我的做法是将每种路径到达终点的步数都存在一个hash表里面，

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX = 30;

int n = 5;
char G[MAX][MAX];
bool visited[MAX][MAX];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
const int INF = 100000000;
int minS = INF;
int a[100];
void DFS(int i,int j,int step){

//	visited[i][j] = true;
	
	if(G[i][j] == 'S'){
		if(step<=minS){			//找最小的步数,有多种相同的情况，所以要小于或等于 
			minS = step;
			a[minS]++;
		}	
		return;
	}
	visited[i][j] = true;
	
	for(int k = 0;k<4;k++){			//四个方向 
		int nx = i+dx[k];
		int ny = j+dy[k];
		if(0<=nx&&nx<n && 0<=ny&&ny<n && G[nx][ny]!='*' && !visited[nx][ny]){
			visited[nx][ny] = true;		//标记访问 
			DFS(nx,ny,step+1);			//dfs 
			visited[nx][ny] = false;	//回溯 
		}
	}
}
int main(){
	int i,j;
	for(i = 0;i<n;i++)
		for(j = 0;j<n;j++){
			cin>>G[i][j];
		}
	DFS(0,0,0);
//	cout<<minS<<endl;
	for(int i = 0;i<100;i++){
		if(a[i]>0){
			cout<<a[i]<<endl;
			break;
		}
	}
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

善良先生

TA的其他文章

你可能喜欢

【明明的随机数】（C语言代码）

整除问题（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

40.殊途同归-题解(C++代码)

评论区

精彩推荐

计算质因子（C++代码）

C语言训练-大、小写问题（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

小O的图案（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

善良先生

TA的其他文章

你可能喜欢

【明明的随机数】 （C语言代码）

整除问题 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

40.殊途同归-题解(C++代码)

评论区

精彩推荐

计算质因子 （C++代码）

C语言训练-大、小写问题 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

1231题解(注意理解“输入多个测试实例”)

小O的图案 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

【明明的随机数】（C语言代码）

整除问题（C语言代码）

　　评论区

计算质因子（C++代码）

C语言训练-大、小写问题（C语言代码）

小O的图案（C语言代码）