- 浏览: 201988 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
具体代码如下:
#include<iostream>
#include<queue>
using namespace std;
struct point
{
int x,y;
int step;
};
int flag[45][45];
char map[45][45];
int dir1[4][2]={{0,-1},{1,0},{0,1},{-1,0}};//zuo优先
int dir2[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//you优先
int d1,d2;
int start[2];
int end[2];
int w,h;
void init()
{
memset(flag,0,sizeof(flag));
cin>>w>>h;
for(int i=0;i<h;i++)
{
cin>>map[i];
for(int j=0;j<w;j++)
{
if(map[i][j]=='#')
{
flag[i][j]=1;
}
if(map[i][j]=='S')
{
start[0]=i;
start[1]=j;
}
if(map[i][j]=='E')
{
end[0]=i;
end[1]=j;
}
}
}
if(start[0]==0)
{
d1=1;
d2=1;
}
else if(start[0]==h-1)
{
d1=3;
d2=3;
}
else if(start[1]==w-1)
{
d1=2;
d2=0;
}
else
{
d1=0;
d2=2;
}
}
int dfs(int x,int y,int d,int dir[][2])
{
int step ,temp, tempx,tempy;
if(x==end[0]&&y==end[1])
return 1;
for(int i=0;i<4;i++)
{
temp=(d+i)%4;
tempx=x+dir[temp][1];
tempy=y+dir[temp][0];
if(tempx>=0&&tempx<h&&tempy>=0&&tempy<w&&!flag[tempx][tempy])
break;
}
step=dfs(tempx,tempy,(temp+3)%4,dir)+1;
return step;
}
int bfs()
{
memset(flag,0,sizeof(flag));
queue<point> q;
point p;
p.x=start[0];
p.y=start[1];
p.step=1;
flag[p.x][p.y]=1;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
if(p.x==end[0]&&p.y==end[1])
return p.step;
for(int i=0;i<4;i++)
{
point temp;
temp.x=p.x+dir1[i][1];
temp.y=p.y+dir1[i][0];
if(temp.x>=0&&temp.x<h&&temp.y>=0&&temp.y<w&&map[temp.x][temp.y]!='#'&&!flag[temp.x][temp.y])
{
flag[temp.x][temp.y]=1;
temp.step=p.step+1;
q.push(temp);
}
}
}
return 0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
init();
cout<<dfs(start[0],start[1],d1,dir1)<<" ";
cout<<dfs(start[0],start[1],d2,dir2)<<" ";
cout<<bfs()<<endl;
}
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 836虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 841选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 866题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 982题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 967字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1441题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 1016大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1610题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2710是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1269在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 801从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2392题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1107题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1256大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 991大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 1003题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2170大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1623题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1257题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 948题意:Ted今年100岁,给出n对他家族的关系:“父 ...
相关推荐
两个解决方案的代码文件“POJ1753-Flip Game(BFS+bit).cpp”和“POJ1753-Flip Game(DFS+enum).cpp”分别实现了BFS和DFS策略。阅读这些代码可以帮助理解如何将理论转换为实际的程序实现。 五、文档说明 “POJ1753-...
poj2488、poj3083等是DFS的练习,poj3278、poj1426等是BFS的题目。 5. **动态规划**和**数学**:poj1837、poj1276是简单的动态规划问题,poj3267、poj1836等进一步强化了DP,poj3252、poj1850等则涉及组合数学,poj...
它涉及了数据结构(如并查集)、搜索算法(如DFS或BFS)以及几何问题的处理,对于提升编程竞赛技巧非常有帮助。通过解决这个问题,程序员可以深入理解如何在实际问题中运用计算机科学的基本原理。
八数码问题的解题核心在于搜索算法,常见的有深度优先搜索(DFS)、宽度优先搜索(BFS)以及A*搜索等。其中,BFS通常能保证找到最短的步数,但空间复杂度较高。对于大型问题,特别是立体版本,可能会消耗大量内存。...
背包问题 动态规划 POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 ...
- POJ 2488、POJ 3083:利用DFS遍历图或树。 - POJ 3009、POJ 1321:基于DFS的问题求解。 #### 广度优先搜索 (BFS) - **题目示例**: - POJ 2251:BFS的应用场景。 #### 其他搜索算法 - **题目示例**: - POJ ...
在实际编程实践中,理解并熟练运用简单搜索算法是基础,随着能力的提升,还会接触到更高级的搜索算法,如深度优先搜索(DFS)、广度优先搜索(BFS),以及二叉搜索树等更复杂的搜索结构。在POJ平台上不断挑战和解决...
包括深度优先遍历(DFS)和广度优先遍历(BFS),用于探索图的所有节点,是解决许多图问题的基础,如poj1860和poj3259所示。 #### 最短路径算法 Dijkstra算法、Bellman-Ford算法和Floyd算法分别适用于无负权边、有...
在实现拓扑排序时,一般采用**深度优先搜索(DFS)**或**广度优先搜索(BFS)**两种方法。DFS直接从入度为0的节点开始,而BFS则利用队列来按顺序处理这些节点。对于poj1094题目,我们需要读取输入文件,构建图的邻接...
常用的搜索算法有深度优先搜索(DFS)、广度优先搜索(BFS)、贪心算法、回溯算法等。 **重要性**:搜索算法是解决许多复杂问题的有效手段。例如,在游戏AI、路径规划等领域有着广泛的应用。 **示例题目**: - POJ...
2. **图的遍历**:DFS和BFS是解决图问题的常用方法,它们可以用来寻找特定路径或计算节点之间的最短路径。 3. **网络破坏策略**:题目可能要求玩家找出最小数量的节点,破坏这些节点将导致整个网络崩溃。这需要对图...
在POJ题目中,BFS常用于最短路径问题、最近公共祖先查询等。比如求解两节点间的最短路径,如果边的权重都为1,BFS将给出答案。 3. **Dijkstra算法**:这是解决单源最短路径问题的经典算法,适用于有向图或无向图,...
在这个问题中,可以使用DFS或BFS来探索从起点到其他节点的所有素数路径。 4. **动态规划(Dynamic Programming, DP)**:虽然这不是必需的,但一些复杂的问题可以通过DP来优化求解过程,比如预计算某些节点是否为...
- (poj1328, poj2109, poj2586):介绍各种搜索算法,如深度优先搜索(DFS)、广度优先搜索(BFS)等。 3. **排序与查找**: - 提供对排序和查找算法的理解与应用指导,包括快速排序、归并排序、二分查找等经典...
“POJ2706-Connect”是一个关于图的连通性问题,通过DFS或BFS算法可以求解。解题者提供的代码已经通过了系统测试,而解题报告则进一步解析了代码的实现细节。学习这类问题有助于提升对图论的理解和编程技巧,对参加...
可能涉及的经典算法有分治策略、贪心算法、回溯法、动态规划、图算法(如DFS、BFS、最短路径算法)等。每个子文件中的代码都是对特定问题的算法实现。 4. 数据结构:有效的数据结构是解决问题的关键。常见数据结构...
1. 深度优先搜索(DFS):如POJ2488、POJ3083等,常用于解决图和树的问题。 2. 广度优先搜索(BFS):如POJ3278、POJ1426,适用于寻找最短路径等。 3. 搜索技巧与剪枝:优化搜索效率,如POJ2531、POJ1416。 五、...
4. **深度优先搜索(DFS)** 和 **广度优先搜索(BFS)**:这两种遍历方法是图算法的基础,常用于寻找路径、判断连通性、检测环路等。DFS通过递归或栈实现,而BFS使用队列进行。 5. **二分图匹配**:匈牙利算法或...
POJ1039-Pipe可能需要应用到的算法包括但不限于深度优先搜索(DFS)、广度优先搜索(BFS)、动态规划、贪心算法或图的遍历算法。 4. **图论**:由于题目名为"Pipe",很可能涉及到图的结构,比如管道之间的连接可以...