DFS利用递归，不必使用多余的数据结构，实现简单。但要注意剪枝。
BFS借助队列，往往在求最优解时使用。总是能找到最优解，某些情况下也要剪枝。
这两种方法根据具体问题来使用。
以此题为例，DFS和BFS都可求解。
由于是求最优解，用BFS更为直接。
由于此题的不确定性，必须要考虑所有可能情况，结合剪枝。
题目1091：棋盘游戏
时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：616
解决：151
题目描述：
有一个6*6的棋盘，每个棋盘上都有一个数值，现在又一个起始位置和终止位置，请找出一个从起始位置到终止位置代价最小的路径：
1、只能沿上下左右四个方向移动
2、总代价是没走一步的代价之和
3、每步（从a,b到c,d）的代价是c,d上的值与其在a,b上的状态的乘积
4、初始状态为1
每走一步，状态按如下公式变化：（走这步的代价%4）+1。
输入：
第一行有一个正整数n，表示有n组数据。
每组数据一开始为6*6的矩阵，矩阵的值为大于等于1小于等于10的值，然后四个整数表示起始坐标和终止坐标。
输出：
输出最小代价。
样例输入：
1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 5 5
样例输出：
23
BFS代码：
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
int x, y, sum, statu;
};
int ans;
int map[6][6];
int opt[6][6][4]; //记录最优解,剪枝条件。4中状态都要记录
Node start;
int ex, ey;
int cnt = 0;
int dir[4][2] = {{ 0, 1 },{ 1, 0 },{ 0, -1 },{ -1, 0 } };
queue<Node> q;
void bfs(Node n)
{
q.push(n);
int tempx, tempy, cost;
while (!q.empty())
{
cnt++;
Node tn = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
tempx = tn.x + dir[i][0];
tempy = tn.y + dir[i][1];
if (tempx >= 0 && tempx < 6 && tempy >= 0 && tempy < 6)
{
cost = tn.statu * map[tempx][tempy];
//如果这一步比以前的某一步代价还大 或者 比到终点的代价还大
if (tn.sum + cost < opt[tempx][tempy][cost % 4 ] && tn.sum + cost < opt[ex][ey][cost % 4 ])
{
opt[tempx][tempy][cost % 4] = tn.sum + cost;
Node temp;
temp.x = tempx;
temp.y = tempy;
temp.sum = tn.sum + cost;
temp.statu = cost % 4 + 1;
q.push(temp);
}
}
}
}
}
int main()
{
int k;
cin >> k;
while (k--)
{
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
{
cin >> map[i][j];
for(int k=0; k<4; k++)
opt[i][j][k] = 100000;
}
start.sum = 0;
start.statu = 1;
ans = 100000;
cin >> start.x >> start.y >> ex >> ey;
bfs(start);
for (int i = 0; i < 4; i++)
{
if (ans > opt[ex][ey][i])
ans = opt[ex][ey][i];
}
//cout << cnt << endl;
cout << ans << endl;
}
return 0;
}
DFS代码;
#include <iostream>
using namespace std;
int map[6][6];
int sx,sy,ex,ey,ans;
int cnt = 0;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
bool visit[6][6];
void dfs(int x,int y,int sum,int statu){
cnt ++;
if(sum < ans){
if(x == ex && y == ey){
ans = sum;
return;
}
for(int i=0; i<4; i++){
int tempx = x + dir[i][0];
int tempy = y + dir[i][1];
if(visit[tempx][tempy] && tempx >=0 && tempx < 6 && tempy >=0 && tempy < 6){
int cost = statu * map[tempx][tempy];
visit[tempx][tempy] = false;
dfs(tempx, tempy, sum+cost, cost % 4 + 1);
visit[tempx][tempy] = true;
}
}
}
}
int main() {
int k;
cin >> k;
while(k--){
for(int i=0; i<6; i++)
for(int j=0; j<6; j++){
cin >> map[i][j];
visit[i][j] = true;
}
cin >> sx >> sy >> ex >> ey;
ans = 1000000;
dfs(sx,sy,0,1);
//cout << cnt << endl;
cout << ans << endl;
}
return 0;
}
分享到：
相关推荐
DFS和BFS DFS（Depth-First-Search）深度优先搜索算法，是搜索算法的一种。是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点 宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法...
图的遍历方式包括DFS BFS,这个工程文件是俩种遍历方式的实现，适合学习用，工程实践还得加工，具体分析 在我的博客 数据结构练习 10
代码中包括了图的BFS和DFS遍历还包括了寻找最短路径，给定路长寻找路径，生成图，添加结点，删除节点
数据结构中重要的部分之一——图，这里主要完成一个无向无环图的建立，然后进行DFS BFS的遍历，输出结果，初学图和DFS BFS的小伙伴可以来看看噢
DFS和BFS算法的实现，使用C++语言，适合数据结构初学者学习。
基于邻接表存储的图的dfs与bfs遍历，对学习数据结构很有帮助
定义采用邻接矩阵存储的图结构封装DFS、BFS算法
dfs和bfs.pptx
封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法 上机作业： 定义采用邻接矩阵存储的图结构
图的dfs和bfs实现，可执行程序，数据结构第11次上机作业
重传Java实现DFS,BFS，上次传的没有成功，导致几位朋友下了没看到东西。
实现了图的DFS和BFS算法，实现语言C++
dfs-bfs-master 网上找到的 dfs和bfs演示
基于DFS和BFS广度优先搜索算法的路线搜索算法仿真+含代码操作演示视频 运行注意事项：使用matlab2021a或者更高版本测试，运行里面的Runme.m文件，不要直接运行子函数文件。运行时注意matlab左侧的当前文件夹窗口...
实验内容及要求： 用字符文件提供数据建立连通无向图...编写程序，实现DFS与BFS算法，输出DFS与BFS生成树的每条边。（边用顶点序号组成的无序偶表示） 实验目的：掌握图的邻接表存储结构；掌握图的遍历算法与生成树。
使用邻接表结构，进行广度优先搜索、深度优先搜索并生成树或生成森林，并打印树的边
图以及DFS和BFS的实现 前提，目标和结果 前提: 完成本次作业，学生需要掌握如下知识 • 图的存储- 有关图的存储的数据结构 • 图的便利-有关深度优先搜索和广度优先搜索的知识
这是山东大学可视化课程项目，用js实现的BFS和DFS，详细的展示了BFS和DFS的运行过程，网页可交互。
dfs和bfs算法 DFS（深度优先搜索）和BFS（广度优先搜索）是两种用于遍历或搜索树或图的算法。它们的主要区别在于访问节点的顺序。 1. **深度优先搜索（DFS）** 深度优先搜索是一种用于遍历或搜索树或图的算法。这...
数据结构实验报告 DFS和BFS算法.doc