#include &stdio.h&
#include &stdlib.h&
#include &string.h&
struct node{//各个位置的坐标,距起点距离用结构体封装起来
struct node queue[100];//队列实现BFS
int head=0,tail=0;
int map[51][51];//存图
int book[51][51];//标记走过的点
//图的规模
int locx,//小哈位置
//假设小哼位于(1,1)
int next[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//当前位置的下一位置的坐标选择
bfs(int x,int y)//x,y为当前head的坐标,bfs为以当前head为基础进行queue拓展，即广搜
if(x==locx&&y==locy){
return queue[head].
for(int i=0;i&4;i++){//依次看看上下左右符不符合情况
int xnext=x+next[i][0];
int ynext=y+next[i][1];
if(xnext&=1&&xnext&=n&&ynext&=1&&ynext&=n&&map[xnext][ynext]==1&&book[xnext][ynext]==0){
book[xnext][ynext]=1;
queue[tail].x=
queue[tail].y=
queue[tail].distance=queue[head].distance+1;
head++;//当前head广搜完，head后移
return bfs(queue[head].x,queue[head].y);
int main()
//初始化book数组
for(int i=0;i&=50;i++)
memset(book[i],0,sizeof(book[i]));
scanf("%d",&n);
scanf("%d%d",&locx,&locy);
//读入map,非障碍物存1
for(int i=1;i&=n;i++)
for(int j=1;j&=n;j++)
scanf("%d",&map[i][j]);
//初始化队列
queue[tail].x=1;
queue[tail].y=1;
queue[tail].distance=0;
book[1][1]=1;
int min=bfs(1,1);
printf("%d\n",min);
啊哈！算法—深度优先搜索DFS—解救小哈
小哈去玩迷宫，结果迷路了，小哼去救小哈。迷宫由n行m列的单元格组成（n和m都小于等于50），每个单元格要么是空地，要么是障碍物。
问题：帮小哼找到一条从迷宫的起点通往小哈所在位置的最短路径。（注意：障...
《啊哈算法》第四章 万能的搜索
参考：《啊哈算法》这里的搜索与图的遍历要区分开，这里只是对数的搜索进行尝试，常用于地图搜索什么，查找是否通路什么的。...
[Aha]解救小哈
题目：见啊哈算法P81页。
分析：最常见的DFS配合最短路，熟悉写法。
代码：#include
int n , m , p , q ,...
啊哈算法搜索应用之宝岛探险(BFS和DFS)
struct node{
struct node queue[100];//队列...
深度优先算法：《啊哈！算法》一书中第四章“解救小哈”例子的 C++ 语言实现
深度优先（Depth First Search, DFS）算法，《啊哈！算法》一书中第四章“解救小哈”例子的 C++ 语言实现。...
书上的例子是从右开始的，还强调了几次必须。
为什么一定要从右边开始呢？
让我们来试试从左边开始会怎样~
还是用了书上的例子：
不过我们是从 i 向右走开始
前面几步的 i , j 换位没出现什么问...
Time Limit: MS (Java/Others)
Memory Limit: KB (Java/Others)Submit
作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了...
本程序在VS2013下调试通过，若有疑问可以评论大家探讨// DFS.cpp : Defines the entry point for the console application.
啊哈算法DFS应用之解救小哈
int book[51][51];//标记走过的点
int map[51][51];//存图
int next[4][2]={{-1,0},{1,0},{0,-...
没有更多推荐了，先挂题目：
有两个无刻度标志的水壶，分别可装升和升（为整数，、）的水。设另一方面有一水缸，可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。已知升为满壶，升为空壶。问如何通过倒水或灌水操作用最少步数能在升壶中量出（）升的水来。
一行：x,y,z
每一行为一个步骤，输出步骤数和x、y水壶里面的水（输出时注意：本着节约用水的原则，因此，优先两个水壶互相倒水，无法达到目的时，再考虑，将水浪费掉）
格式控制符为：sep%3d:%5d%5d
如果无解则输出
No answer！
这道题与一般的水缸灌水有一定区别，一般的水缸灌水只需要输出需要的最小步数而这道题需要输出每一步的水壶中的水量并且要节约用水（我做的时候被坑得要死）。
根据题意我们可以看出一共有六种情况：
1、a壶倒空，2、b壶倒空，3、a壶倒满，4、b壶倒满
5、a壶倒入b壶中（1）b壶倒满，a壶没有剩余（2）b壶倒满，a壶有剩余
6、b壶倒入a壶中（1）a壶倒满，b壶没有剩余（2）a壶倒满，b壶有剩余
通过这六种情况可以建立一个函数，把这六步遍历一遍即可。
代码如下：
#include&cstdio&
#include&cstdlib&
struct cup{
int a,b,z,tail=2;
bool f[110][110],s[110][110];
cup q[1010];
void water(cup in){
if(f[in.x][in.y])
f[in.x][in.y]=1;
if(in.x+in.y&=b){
//a桶倒入b桶中，能否倒满
p.y=in.x+in.y;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
p.x=in.x+in.y-b;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
if(in.x+in.y&=a){
//b桶倒入a桶中，能否倒满
p.x=in.x+in.y;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
p.y=in.x+in.y-a;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
if(s[p.x][p.y]==0){
q[tail]=p;
q[tail].step++;
q[tail].upa=in.x;
q[tail].upb=in.y;
s[p.x][p.y]=1;
void bfs2(int za,int zb){
if(q[k].x==za&&q[k].y==zb){
printf("sep%3d:%5d%5d\n",q[k].step,q[k].x,q[k].y);
while(k&tail){
if(q[k].x==za&&q[k].y==zb){
bfs2(q[k].upa,q[k].upb);
printf("sep%3d:%5d%5d\n",q[k].step,q[k].x,q[k].y);
bool flag=0;
void bfs(int cur){
while(k&tail){
if(q[k].y==cur){
water(q[k]);
if(!flag) printf("No answer!");
bfs2(q[k].upa,q[k].upb);
printf("sep%3d:%5d%5d\n",q[k].step,q[k].x,q[k].y);
void work(){
scanf("%d%d%d",&a,&b,&z);
q[1].x=a;q[1].y=0;
q[1].step=0;
s[a][0]=1;
int main(){
1.六步操作遍历时有先后顺序，仔细思考！
2.可用queue替代数组，代码可变精简。
C++解决 倒水算法
题目：倒水算法
1.指定水杯个数；
2.指定各个水杯的容量；
3.指定各水杯的当前水量；
4.倒水时遵循两个原则：a)将杯子倒满；b)将有水的杯子中的水全部倒干净。
5.最后达到指定的水平。...
NYOJ 92--图像有用区域【BFS && 水题】
图像有用区域
时间限制：3000 ms
内存限制：65535 KB
“ACKing”同学以前做一个图像处理的项目时，遇到了一个问题，他需要摘取出...
c++ BFS模板题 水缸灌水 题解
题目描述：
有两个无刻度标志的水壶，分别可装x升和y升（x,y为整数，x、y）的水。设另一方面有一水缸，可用来向水壶灌水或倒出水，两水壶间，水也可以相互倾灌。已知x升为满壶，y升为空壶。问如何通过倒水...
&em&C%2B%2B&/em&图像处理编程配合清华的c/c++数字图像处理... &em&C%2B%2B&/em&图像处理编程配合清华的c/c++数字图像处理 综合评分:0 收藏(1)评论举报 所需: 3积分/C币 开通VI...
*版权证明: 只允许上传png/jpeg/jpg/gif格式的图片,且小于3M
*详细原因:
交 &em&C%2B%2B&/em& C++ 常用例程源代码 3积分 立即下载 ...
https://hellogithub.com/periodical/category/C%2B%2B%20%E9%A1%B9%E7%9B%AE/https://github.com/ytchhh/p...
http://download.csdn.net/tag/Programming.Principles%2Band%2BPractice%2BUsing%2BC%2B%2B
下载 & 资源分类 & 开发技术 & C & 达内科技&em&C%2B%2B&/em&课件%2B及%2B源码%2B笔记【完美版】 达内科技&em&C%2B%2B&/em&课件%2B及%2B源码%2B笔记【完美版】 ...
【codevs1226】倒水问题，BFS练习
1226 倒水问题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
有两个无刻度标志的水壶，分别可装 x ...
没有更多推荐了，题目链接：
题目大意：
用一个5*5的二维数组表示迷宫，输出左上角到右下角的最短路径。
用BFS求最短路径。用pre[]来记录每个状态之前的状态，然后递归输出路径。
#include&iostream&
#include&algorithm&
#include&cstdio&
#include&cstring&
int Map[6][6],vis[6][6],pre[110];
//pre[]记录每个状态的前一个状态
struct Cam
}List[110];
int Dire[4][2] = {-1,0,1,0,0,-1,0,1};
//上下左右四个方向
int Go(int x,int y) //判断是否可走
if(x &= 0 && x & 5 && y &= 0 && y & 5 && Map[x][y] == 0)
void Print(int x)
//输出路径
t = pre[x];
if(t == 0)
printf("(0, 0)\n");
printf("(%d, %d)\n",List[x].x,List[x].y);
printf("(%d, %d)\n",List[x].x,List[x].y);
void BFS()
memset(vis,0,sizeof(vis));
int Head = 0,Tail = 1;
List[0].x = 0;
List[0].y = 0;
pre[0] = -1;
while(Head & Tail)
int x = List[Head].x;
int y = List[Head].y;
if(x == 4 && y == 4)
Print(Head);
for(int i = 0; i & 4; ++i)
int xx = x + Dire[i][0];
int yy = y + Dire[i][1];
if( !vis[xx][yy] && Go(xx,yy) )
vis[xx][yy] = 1;
List[Tail].x =
List[Tail].y =
pre[Tail] = H
int main()
for(int i = 0; i & 5; ++i)
for(int j = 0; j & 5; ++j)
scanf("%d",&Map[i][j]);
poj3984（迷宫问题）（bfs和队列）
嘿嘿，如果这道题是求最短的步数，那么用BFS算法就可以了。但是因为还要输出路径，可能还要保存每个结点的上一个结点的坐标，最后再用递归或是迭代的方法逆序输出坐标，博主昨天学会了bfs算法表示真的很高兴，...
POJ3984迷宫问题（BFS+队列+栈）
POJ-3984-迷宫问题
http://poj.org/problem?id=3984
大概思路：进行普通的BFS，用队列来操作。在保存路径的时候，可以用栈来输出路径，利用先进后出的特性。...
poj 3984 迷宫问题
做这道题其实我是想看看打印路径的方法，挺水的，看了网上别人的代码，打印路径基本上都是保存一下父节点，然后
打印出它的坐标，我写的是递归一下，从后面向前找到起点，找的过程有点不一样，之前没保存，而是继...
poj-3984-迷宫问题
原文链接 ：poj-3984-迷宫问题
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 256...
回溯原来的节点用到两个栈：第一个栈用来将队列中的结点按照入队顺序压入栈，(0,0)节点首先被压入栈.
第二个栈用来记录路径,将第一个栈的栈顶元素依次[根据是不是路径上的节点]压入第二个栈,(0,0...
4127: 迷宫问题
代码很简单，学会使用BFS可以很快解决此类问题
const int maxn = 65536;
int c[4][2] = {0,1,1,0,0,-...
poj3984迷宫问题（如何输出最短路）
题目：迷宫问题Time Limit:1000MS
Memory Limit:65536KB
64bit IO Format:%lld & %lluDescription
定义一个二维...
POJ 3984:迷宫问题【BFS】
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 11603
Accepted...
POJ3984 迷宫问题 BFS
看题传送门：http://poj.org/problem?id=3984
明天帮学弟挑电脑顺便去玩。接下来几天好好看数据结构。嗯哼。
这题标准的BFS应用，唯一需要注意的是需要输出中...
dfs 求迷宫路径
题目地址：http://poj.org/problem?id=3984
利用图论中深搜的思想，存在边就是x,y -&
还有x,y -& x,y+1
然后仍然是访问未访问的而且不是墙...
没有更多推荐了，posts - 390,&
comments - 57,&
trackbacks - 0
时间限制： ms &|& 内存限制：65535 KB
Many of us had played the game "Battle city" in our childhood, and some people (like me) even often play it on computer now. What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers, steel walls and brick walls only. Your task is to get a bonus as soon as possible suppose that no enemies will disturb you (See the following picture). Your tank can't move through rivers or walls, but it can destroy brick walls by shooting. A brick wall will be turned into empty spaces when you hit it, however, if your shot hit a steel wall, there will be no damage to the wall. In each of your turns, you can choose to move to a neighboring (4 directions, not 8) empty space, or shoot in one of the four directions without a move. The shot will go ahead in that direction, until it go out of the map or hit a wall. If the shot hits a brick wall, the wall will disappear (i.e., in this turn). Well, given the description of a map, the positions of your tank and the target, how many turns will you take at least to arrive there?
输入The input consists of several test cases. The first line of each test case contains two integers M and N (2 &= M, N &= 300). Each of the following M lines contains N uppercase letters, each of which is one of 'Y' (you), 'T' (target), 'S' (steel wall), 'B' (brick wall), 'R' (river) and 'E' (empty space). Both 'Y' and 'T' appear only once. A test case of M = N = 0 indicates the end of input, and should not be processed.输出For each test case, please output the turns you take at least in a separate line. If you can't arrive at the target, output "-1" instead.样例输入
1 /* 功能Function Description:
开发环境Environment:
DEV C++ 4.9.9.1
技术特点Technique:
版本Version:
作者Author:
备注Notes:
本题应该使用优先队列的，表示不会，就只能用数组模拟手动排序了，因为每次加入的节点的优先级可能不同（访问到砖块的要2单位时间，而访问到空白的只需1单位时间）
所以要对队列中的step进行从小到大排序这样搜索得到的才是正确的解。
13 //代码一：
14 #include&cstdio&
15 #include&stdlib.h&
17 char map[310][310];
18 int m,n;
19 int dir[4][2]={-1,0,0,1,1,0,0,-1};
21 typedef struct point
26 int cmp(const void *p,const void *q)
return (*(point *)p).step-(*(point *)q).
31 int BFS(point s,point t)
point q[10000];
int head,tail,i;
head=tail=1;
q[tail++]=s;
while(head!=tail)
s=q[head++];
if(s.x==t.x&&s.y==t.y)
for(i=0;i&4;++i)
temp.x=s.x+dir[i][0];
temp.y=s.y+dir[i][1];
if(temp.x&=0||temp.x&n||temp.y&=0||temp.y&m)
if(map[temp.y][temp.x]=='S'||map[temp.y][temp.x]=='R')
else if(map[temp.y][temp.x]=='B')
temp.step=s.step+2;
map[temp.y][temp.x]='S';
temp.step=s.step+1;
map[temp.y][temp.x]='S';
q[tail++]=
qsort(&q[head],tail-head,sizeof(point),cmp);
return -1;
68 int main()
point s,t;
while(scanf("%d%d",&m,&n),m||n)
getchar();
for(i=1;i&=m;++i)
for(j=1;j&=n;++j)
scanf("%c",&map[i][j]);
if(map[i][j]=='Y')
map[i][j]='S';
else if(map[i][j]=='T')
getchar();
printf("%d\n",BFS(s,t));
101 //代码二：------优先队列（转）
102 #include &iostream&
103 #include &queue&
104 #include &cstdio&
105 #include &cstring&
106 using namespace
107 #define
108 char map[max][max];
109 int n,m;
110 bool vist[max][max];
111 int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
113 struct node
int x,y,c;
friend bool operator &(const node &s1,const node &s2)
return s1.c&s2.c;
121 node s,e;
123 int bfs()
priority_queue & node &
memset(vist,0,sizeof(vist));
node now,t;
q.push(s);
vist[s.x][s.y]=1;
while (!q.empty())
now=q.top();
if (now.x==e.x&&now.y==e.y)
return now.c;
for (int i=0;i&4;i++)
t.x=now.x+d[i][0];
t.y=now.y+d[i][1];
if (t.x&=0&&t.x&n&&t.y&=0&&t.y&m&&!vist[t.x][t.y])
vist[t.x][t.y]=1;
if (map[t.x][t.y]=='B')
t.c=now.c+2;
q.push(t);
if (map[t.x][t.y]=='E'||map[t.x][t.y]=='T')
t.c=now.c+1;
q.push(t);
return -1;
163 int main()
while (cin&&n&&m,m+n)
for (i=0;i&n;i++)
for (j=0;j&m;j++)
cin&&map[i][j];
if (map[i][j]=='Y')
s.x=i,s.y=j;
if (map[i][j]=='T')
e.x=i,e.y=j;
int sum=bfs();
cout&&sum&&
阅读(...) 评论()时间限制：2s，空间256MB
实现一个队列，完成以下功能：
查询队列中位置Y是谁
一开始队列为空，队列中的位置从1开始（即队头从1开始）。
第一行一个整数n，表示操作个数（1 &= n &= 100000）
接下来n行，每行第一个数字表示操作（见描述）：
若为数字1，则接下来有一串字符串X，表示将X加入队列中。
若为数字2，表示出列（保证队列非空），并输出出列的这个人。
若为数字3，则接下来有一个整数Y，表示询问队列中位置Y是谁（保证位置Y合法），并输出名字。
数据中的字符串只包含26个小写字母（无空格灯分隔符），且长度不超过15
字符串可能有重复，正如现实中可能有重名。
将所有操作2和操作3输出，一行一个。
1 sdfasdasgeqsadg
sdfasdasgeqsadg
C++或JAVA所提供的queue类并未直接提供队列中元素的索引，所以可能需要你自己写一个队列。
#include &bits/stdc++.h&
using namespace std;
string Queue[100000];
void enqueue(string name) {
Queue[tail++] =
string dequeue() {
return Queue[head++];
string query(int pos) {
return Queue[head + pos - 1];
int main() {
scanf("%d", &n);
char name[20];
for (; n--; ) {
scanf("%d", &op);
if (op == 1) {
scanf("%s", name);
enqueue(name);
} else if (op == 2) {
printf("%s\n", dequeue().c_str());
scanf("%d", &pos);
printf("%s\n", query(pos).c_str());
如果保证在整个过程中，队列中人数都不回超过k，但入队的次数会超过k,如何用一个大小为k的数组解决？
—循环队列：若head或tail达到了数组的最大长度位置，则让head或tail=0。
#include &bits/stdc++.h&
using namespace std;
string Queue[100000];
void enqueue(string name) {
Queue[tail++] =
if(tail == N)
string dequeue() {
string ret = Queue[head++];
if(head == N)
string query(int pos) {
int p = head + pos - 1;
if(p &= N)
return Queue[p];
int main() {
scanf("%d", &n);
char name[20];
for (; n--; ) {
scanf("%d", &op);
if (op == 1) {
scanf("%s", name);
enqueue(name);
} else if (op == 2) {
printf("%s\n", dequeue().c_str());
scanf("%d", &pos);
printf("%s\n", query(pos).c_str());
清华大学算法训练营——程序十：序列计数
给定一个n个整数的序列以及一个非负整数d，请你输出这个序列中有多少个连续子序列（长度大于1），满足该子序列的最大值最小值之差不大于d。
连续子序列：序列1 2 3中长度大于1的连续子序列有：...
时间限制：2s，空间256MB
实现一个栈，完成以下功能：
查询栈中位置Y是谁
一开始栈为空，栈中的位置从1开始（即栈底位置为1）。
重编码(priority_queue)
有一篇文章，文章包含 n种单词，单词的编号从 1 至 n，第 i 种单词的出现次数为 w[i]。
现在，我们要用一个 2 进制串（即只包含 ...
等式（并查集）
时间限制：2s，空间256MB
n个变量和m个“相等”或“不相等”的约束条件，请你判定是否存在一种赋值方案满足所有m个约束条件。
第一行一个整数T，表...
从实验室出来后，你忽然发现你居然把自己的电脑落在了实验室里，但是实验室的老师已经把大门锁上了。更糟的是，你没有那个老师的电话号码。你开始给你知道的所有人打电话，询问他们有没有老师的电话，...
道路升级（Kruscal）
Z国有 n 个城市和 m 条双向道路，每条道路连接了两个不同的城市，保证所有城市之间都可以通过这些道路互达。每条道路都有一个载重量限制，这限制了通过这条道...
你有足够多的象棋“车”，在一个n×n的棋盘上你能放多少个“车”呢？注意，所给棋盘上有些位置不能放任何东西。同时，某一行（列）最多只能存在一个“车”。
第一行为一个正整数n。（1&...
A：贪心+暴力
链接：大吉大利，今晚吃鸡——枪械篇
思路：我用了一个map使配件种类对应一个最大威力的配件。然后暴力判断每把枪都装上最优的配件以后的威力，求一个极大值即可。
#include...
时间限制：1 sec空间限制：256 MB问题描述邓老师有一个大转盘，被平分成了 2^n 份。邓老师还有一个长度为 2^n 的数组 a（下标从 0 开始），其中的每个元素都是 0 或 1。于是邓老师就...
没有更多推荐了，