链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=91
结题报告:因该说10多天没有A题了,今天过了一道比较水的题目,也算是来纪念一下吧,最近在刷搜索的时候感觉bfs有些题目是比较难的,象蛇和梯子那道题整整卡了我一个星期但是现在仍然没有过,标记一下,有时间在回来看一下!
这道题注意两个地方,一个是下标的值,一个是vis数组标记!
#include<cstdio> #include<cstring> #include<queue> using namespace std; const int dir[8][2] = {-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1}; int mp[9][9]; int vis[9][9]; struct node { int x,y; int step; }; queue<node>Q; int ex,ey,sx,sy; int bfs(node p) { node now,next; Q.push(p); while(!Q.empty()) { now=Q.front(); Q.pop(); for(int i=0;i<8;i++) { int xx = now.x+dir[i][0]; int yy = now.y+dir[i][1]; if(xx<1||xx>8||yy<1||yy>8) continue; if(xx == ex && yy == ey) { return now.step + 1; } if(!vis[xx][yy]) { next.x=xx; next.y=yy; next.step = now.step+1; Q.push(next); } } } } int main( ) { char str1[5],str2[5]; while(scanf("%s%s",str1,str2)!=EOF) { while(!Q.empty()) Q.pop(); sx=str1[0]-'a'+1; sy=str1[1]-'0'; ex=str2[0]-'a'+1; ey=str2[1]-'0'; if(sx==ex&&sy==ey) { printf("To get from %s to %s takes 0 knight moves.\n",str1,str2); continue; } memset(vis,0,sizeof(vis)); vis[sx][sy]=1; node p; p.x = sx; p.y = sy; p.step = 0; printf("To get from %s to %s takes %d knight moves.\n",str1,str2,bfs(p)); } }
相关推荐
这是一道与图论相关的算法问题,主要涉及的是BFS(Breadth First Search,广度优先搜索)算法的应用,用于寻找图中的最短路径。 在描述中提到的"BFS求最短路径"是解决此类问题的关键策略。BFS是一种用于遍历或搜索...
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
Edmonds-Karp算法则是Ford-Fulkerson算法的一种优化版本,它使用了最佳优先搜索(BFS)来寻找增广路径,以确保每次找到的增广路径具有最小的容量限制,从而在有大量边的情况下提高效率。 描述中的"zoj吐血制作,希望...
2. **搜索与图论**:深度优先搜索(DFS)、广度优先搜索(BFS)在图论问题中广泛使用,如最短路径、最小生成树、拓扑排序等。理解和熟练运用这些方法能帮助解决复杂的问题。 3. **动态规划(DP)**:动态规划是一种...
3. **搜索算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、A* 搜索、Dijkstra 算法、Floyd-Warshall 算法等,这些是解决图论问题和路径查找的关键。 4. **动态规划**:背包问题、最长公共子序列、最短路径、...
5. **图论算法**:包括深度优先搜索(DFS)和广度优先搜索(BFS),以及最小生成树(Prim、Kruskal)和最短路径算法(Bellman-Ford、Dijkstra、SPFA)等。这些都是解决图相关问题的核心技术。 6. **字符串处理**:...
5. **搜索与优化**:深度优先搜索(DFS)和广度优先搜索(BFS)是解决图论问题的常用方法,而A*搜索算法或Dijkstra算法则用于寻找最短路径。在实际编程中,为了提高效率,常常需要进行剪枝和启发式搜索。 6. **记忆...
在这个问题中,广度优先搜索(Breadth-First Search,简称BFS)被用来寻找问题的解。BFS是一种图遍历算法,它按照节点的层次顺序依次访问每个节点,先访问离起点近的节点,再访问远的节点。在分油问题中,可能需要...
解决方案可能涉及深度优先搜索(DFS)或广度优先搜索(BFS),以及动态规划等算法,来模拟网络流量的不同路径和可能性,从而找到最优的流量分配方案。 #### 二、FinancialManagement1048:财务决策模型 ...
5. 深度优先搜索(DFS)和广度优先搜索(BFS):这两种图遍历方法是解决许多搜索问题的基础。 6. 字符串处理:涉及字符串匹配、模式查找、编码解码等问题,经常出现在编程竞赛中。 7. 数据结构:如栈、队列、链表...
搜索算法如深度优先搜索(DFS)和广度优先搜索(BFS)用于遍历结构。 在Visual C++中实现这些算法时,需要注意内存管理,避免内存泄漏,以及充分考虑程序的时间复杂度和空间复杂度,以满足比赛对于运行时间和内存...
首先,这些源码揭示了不同类型的算法应用,如动态规划、贪心算法、分治法、回溯法、深度优先搜索(DFS)、广度优先搜索(BFS)等。每种算法都有其特定的应用场景和优化技巧,比如动态规划中的记忆化搜索可以减少重复...
9. **1105FatMouse's Tour.cpp**:题目可能与迷宫求解或最短路径相关,可能要用到深度优先搜索(DFS)或广度优先搜索(BFS)。 10. **1093Monkey and Banana.cpp**:猴子和香蕉的问题可能涉及到动态规划或贪心算法...
2. **搜索算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、二分查找等。 3. **动态规划**:背包问题、最长公共子序列、最短路径问题等。 4. **图论算法**:最小生成树(Prim、Kruskal)、最短路径(Dijkstra、...
本节主要讲解了搜索算法的基础知识,特别是深度优先搜索(DFS)和广度优先搜索(BFS)。 搜索算法是一种通过系统地遍历问题的所有可能解决方案来找到正确答案的方法。它主要分为两类:回溯法和分支限界法。回溯法是...
在解决此类问题时,可以使用图的数据结构,如数组或树形结构,以及图的遍历算法,如深度优先搜索(DFS)或广度优先搜索(BFS)来确定连通性。 课件还提到了解题者需要关注的要点,如解题格式、输入输出格式,以及...
7. 广度优先搜索(BFS):在图或树的遍历中,BFS是从根节点开始,逐层访问所有节点。在提供的代码中,`BFS`函数用于遍历四分树,记录节点信息。 8. 四分树(Quadtree):四分树是一种数据结构,用于存储二维空间的...
在原报告中,作者可能没有选择动态规划或贪心策略,而是采用搜索算法,如深度优先搜索(DFS)或广度优先搜索(BFS),甚至可能结合回溯法来寻找解。这种创新性地运用基础算法,可以启示我们如何在实际问题中灵活应用...
2. **搜索算法**:包括深度优先搜索(DFS)和广度优先搜索(BFS),常用于解决图和树的遍历问题,以及最短路径问题。 3. **图论算法**:如最短路径算法(Dijkstra、Floyd-Warshall)、最小生成树算法(Prim、...
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来确定当前道路网络的连通状态,并计算出最小生成树,如Prim算法或Kruskal算法,以求得最少的新增道路数。 在解题过程中,需要注意输入和输出的格式,确保结果的...