先对比一下DFS和BFS
深度优先搜索DFS 宽度优先搜索BFS
明显可以看出搜索顺序不同。
DFS是搜索单条路径到底部，再回溯。
BFS是搜索近的状态，直到底部，一般在求解最短路径或者最短步数上应用。
BFS要用到队列呢。。
队列的用法看一看
map的基本操作函数： C++Maps 是一种关联式容器，包含“关键字/值”对 begin() 返回指向map头部的迭代器 clear(） 删除所有元素 count() 返回指定元素出现的次数 empty() 如果map为空则返回true end() 返回指向map末尾的迭代器 equal_range() 返回特殊条目的迭代器对 erase() 删除一个元素 find() 查找一个元素 get_allocator() 返回map的配置器 insert() 插入元素 key_comp() 返回比较元素key的函数 lower_bound() 返回键值>=给定元素的第一个位置 max_size() 返回可以容纳的最大元素个数 rbegin() 返回一个指向map尾部的逆向迭代器 rend() 返回一个指向map头部的逆向迭代器 size() 返回map中元素的个数 swap() 交换两个map upper_bound() 返回键值>给定元素的第一个位置 value_comp() 返回比较元素value的函数
map的简单操作函数
练习题系列………………………………………………………
因为步数（折返）的问题撸了一天。。
如果那个点可以走，那么就推入队列，等待搜索。
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
][],step[][];
typedef pair<int, int> P;
struct stu{
int x; int y; int t;
};
];
]={, , , -, };
]={, , , , -};
void zha(int M) {
memset(map1, -, sizeof(map1));
; i < M; i++)
; k < ; k++){//five points are burst.
int nx = ch[i].x + dx[k];
int ny = ch[i].y + dy[k];
&& nx < && ny >= && ny < && (ch[i].t < map1[ny][nx] || map1[ny][nx] == -))
map1[ny][nx] = ch[i].t;//give everypoint the minimum burst time.
}
}
int bfs() {
queue <P> que;
que.push( P (, ));
memset(step, -, sizeof(step));
step[][]=;
while(que.size()) {
P p= que.front();
que.pop();
){//find map1's -1 and print it
return step[p.first][p.second];
}
if(step[p.first][p.second] >= map1[p.first][p.second])continue;//the point had benn burst,so jump it
; i < ; i++) {//this is the point of four diretions that does not been destroy.
int nx = p.first + dx[i],ny = p.second + dy[i];
&& ny >= &&step[nx][ny] == -)//if it can arrive and does not exceed the map
{
que.push(P(nx, ny));//push it to the queue and go
step[nx][ny]=step[p.first][p.second]+;//of course,step must add 1 when go.
}
}
}
;
}
int main()
{
int M,a;
while(~scanf("%d",&M))
{
; i<M; i++)
scanf("%d%d%d",&ch[i].x,&ch[i].y,&ch[i].t);
zha(M);
a=bfs();
printf("%d\n",a);
}
;
}
POJ3669
还是要用个地图标记一下步数，不然会计算错误。
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
typedef pair<int, int> P;
int sx,sy,H,W,N;
][];
][];
] = {,,-,};
] = {,,,-};
void find1(int g){
; i < W; i++)
; k < H; k++)
)){
if(map1[i][k] == 'S') map1[i][k] ='.';
sx = i; sy = k;
return ;
}
}
int bfs(int n)
{
memset(step,-,sizeof(step));
queue <P> que;
que.push(P (sx,sy));
step[sx][sy] = ;
while(que.size()){
int x = que.front().first, y = que.front().second;
que.pop();
; i < ; i++){
int xn = x + dx[i], yn = y + dy[i];
&& xn < W && yn >= && yn < H && map1[xn][yn] != )
{
step[xn][yn] = step[x][y] + ;
))
{
return step[xn][yn];
}
que.push(P(xn, yn));
}
}
}
;
}
int main()
{
cin >> W >> H >> N;
; i < W; i++)
; k < H; k++)
cin >> map1[i][k];
;
find1();
step += bfs();
; i < N; i++)
{
find1(i);
step += bfs(i+);
}
cout << step << endl;
;
}
AOJ0558
#include <iostream>
#include <queue>
#include <string.h>
#include <map>
#include <algorithm>
using namespace std;
]={ , -, , -};
map<string, int> dp;
void bfs(){
queue<string> que;
que.push(");
dp[;
while(que.size()){
string now =que.front();
que.pop();
;
; j < ; j++)
'){
p=j;
break;
}
; i < ; i++){
int pn= p + d[i];
&& pn < && !(p == && i == )
&& !(p == && i == )){
string next = now;
swap(next[p],next[pn]);
if(dp.find(next) == dp.end()){
dp[next] = dp[now] + ;
que.push(next);
}
}
}
}
return ;
}
int main()
{
string line;
bfs();
while(getline(cin,line))
{
line.erase(remove(line.begin(), line.end(), ' '), line.end());
cout << dp[line] << endl;
}
;
}
AOJ0121