BFS路径输出
记录路径
pre存当前点的前一个点的位置标号（序号），类似的还有最长递增子序列的路径记录，还有链式前向星，都是一个方法。
POJ 3984 迷宫问题
题目链接http://poj.org/problem?id=3984
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int m[10][10];
bool vis[10][10];///寻找路径 问题：来过便不再来
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct node
{
int x, y, pre;///a[i].pre存它前一个点在a[]中标号（序号）
}a[30];
void print(node t)
{
vector<node> vec;
while(t.pre != -1)///逆序存放
{
vec.push_back(t);
t = a[t.pre];
}
vec.push_back(a[0]);
int sz = vec.size();
for(int i = sz - 1; i >= 0; --i)
printf("(%d, %d)\n", vec[i].x - 1, vec[i].y - 1);
}
void bfs()
{
int now = 0;
int nxt = 1;
a[now].x = 1;
a[now].y = 1;
a[now].pre = -1;
vis[1][1] = 1;
while(now < nxt)///等效于while(!q.empty())
{
if(a[now].x == 5 && a[now].y == 5)
{
print(a[now]);
return ;
}
for(int i = 0; i < 4; ++i)
{
int xx = a[now].x + dx[i];
int yy = a[now].y + dy[i];
if(xx >= 1 && xx <= 5 && yy >= 1 && yy <= 5 && m[xx][yy] == 0 && !vis[xx][yy])
{
vis[xx][yy] = 1;
a[nxt].x = xx;
a[nxt].y = yy;
a[nxt].pre = now;
nxt++;///搜到终点，周围点条件不满足此if,nxt停增
}
}
now++;
}
}
int main()
{
for(int i = 1; i <= 5; ++i)
for(int j = 1; j <= 5; ++j)
scanf("%d", &m[i][j]);
bfs();
return 0;
}
SDNUOJ 1220 Look for homework
题目链接 http://www.acmicpc.sdnu.edu.cn/problem/show/1220
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
string s[15];
bool vis[15][15];
///“目标方向”逆时针转90°即可，想图（ignore this sentence）
/// D L R U
int dx[] = {1, 0, 0, -1};
int dy[] = {0, -1, 1, 0};
struct node
{
int x, y, pre, step;
char ch;
} a[105];
void print(node t)
{
vector<node> vec;
while(t.pre != -1)
{
vec.push_back(t);
t = a[t.pre];
}
int sz = vec.size();
for(int i = sz - 1; i >= 0; --i)
{
cout << vec[i].ch;
// cout << vec[i].x << ' ' << vec[i].y << '\n';
}
cout << '\n';
}
void bfs()
{
int now = 0;
int nxt = 1;
a[now].x = 0;
a[now].y = 0;
a[now].pre = -1;
a[now].step = 0;
vis[0][0] = 1;
while(now < nxt)
{
if(a[now].x == n - 1 && a[now].y == m - 1)
{
cout << a[now].step << '\n';
print(a[now]);
return ;
}
for(int i = 0; i < 4; ++i)
{
int xx = a[now].x + dx[i];
int yy = a[now].y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && s[xx][yy] == '0')///注意这里是字符0
{
vis[xx][yy] = 1;///又忘了访问后标记
a[nxt].x = xx;
a[nxt].y = yy;
a[nxt].step = a[now].step + 1;
a[nxt].pre = now;
switch(i)
{
case 0:
a[nxt].ch = 'D';
break;
case 1:
a[nxt].ch = 'L';
break;
case 2:
a[nxt].ch = 'R';
break;
default:
a[nxt].ch = 'U';
}
nxt++;
}
}
now++;
}
}
int main()
{
// freopen("00in.txt", "r", stdin);
while(~scanf("%d%d", &n, &m))
{
memset(vis, 0, sizeof(vis));
for(int i = 0; i < n; ++i)
cin >> s[i];
bfs();
}
return 0;
}
POJ 3414 Pots
题目链接 http://poj.org/problem?id=3414
#include <map>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int a, b, c;
bool vis[1005][1005];
map<int, string> mp;
void init()
{
mp[0] = "FILL(1)";
mp[1] = "FILL(2)";
mp[2] = "DROP(1)";
mp[3] = "DROP(2)";
mp[4] = "POUR(1,2)";
mp[5] = "POUR(2,1)";
}
struct status
{
int p1, p2, step, pre;
string s;
} d[1005];
int bfs()
{
memset(vis, 0, sizeof(vis));
int now = 0;
int nxt = 1;
d[now].p1 = 0;
d[now].p2 = 0;
d[now].step = 0;
d[now].pre = -1;
vis[0][0] = 1;
while(now < nxt)
{
// cout << now << ' ' << d[now].p1 << ' ' << d[now].p2 << ' ' << d[now].step << ' ' << d[now].pre << ' ' << d[now].s << '\n';
if(d[now].p1 == c || d[now].p2 == c)
return now;
if(d[now].p1 < a && !vis[a][d[now].p2])
{
vis[a][d[now].p2] = 1;
d[nxt].p1 = a;
d[nxt].p2 = d[now].p2;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[0];
nxt++;
}
if(d[now].p2 < a && !vis[d[now].p1][b])
{
vis[d[now].p1][b] = 1;
d[nxt].p1 = d[now].p1;
d[nxt].p2 = b;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[1];
nxt++;
}
if(d[now].p1 != 0 && !vis[0][d[now].p2])
{
vis[0][d[now].p2] = 1;
d[nxt].p1 = 0;
d[nxt].p2 = d[now].p2;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[2];
nxt++;
}
if(d[now].p2 != 0 && !vis[d[now].p1][0])
{
vis[d[now].p1][0] = 1;
d[nxt].p1 = d[now].p1;
d[nxt].p2 = 0;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[3];
nxt++;
}
if(d[now].p1 != 0 && d[now].p2 < b)/// A -> B
{
if(d[now].p1 >= b - d[now].p2)///A剩的多余B缺的
{
int t = b - d[now].p2;
if(!vis[d[now].p1 - t][b])
{
vis[d[now].p1 - t][b] = 1;
d[nxt].p1 = d[now].p1 - t;
d[nxt].p2 = b;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[4];
nxt++;
}
}
else///A所剩少于B所缺
{
if(!vis[0][d[now].p2 + d[now].p1])
{
vis[0][d[now].p2 + d[now].p1] = 1;
d[nxt].p1 = 0;
d[nxt].p2 = d[now].p2 + d[now].p1;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[4];///注意
nxt++;
}
}
}
if(d[now].p1 < a && d[now].p2 != 0)/// B -> A
{
if(d[now].p2 >= a - d[now].p1)/// B中剩的多
{
int t = a - d[now].p1;
if(!vis[a][d[now].p2 - t])
{
vis[a][d[now].p2 - t] = 1;
d[nxt].p1 = a;
d[nxt].p2 = d[now].p2 - t;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[5];
nxt++;
}
}
else ///A中缺的多
{
if(!vis[d[now].p1 + d[now].p2][0])
{
vis[d[now].p1 + d[now].p2][0] = 1;
d[nxt].p1 = d[now].p1 + d[now].p2;
d[nxt].p2 = 0;
d[nxt].step = d[now].step + 1;
d[nxt].pre = now;
d[nxt].s = mp[5];
nxt++;
}
}
}
now++;///漏了这句
}
return inf;
}
int main()
{
init();
while(~scanf("%d%d%d", &a, &b, &c))
{
int ans = bfs();
if(ans != inf)
{
cout << d[ans].step << '\n';
vector<status> vec;
while(d[ans].pre != -1)
{
vec.push_back(d[ans]);
ans = d[ans].pre;
}
int sz = vec.size();
for(int i = sz - 1; i >= 0; --i)
cout << vec[i].s << '\n';
}
else
cout << "impossible" << '\n';
}
return 0;
}