|
|
Posted on 2012-07-04 22:48 lentty 阅读(225) 评论(0) 编辑 收藏 引用
TOJ 3520 BFS记录路径，每次记录它的前驱，然后从目标点递归回去找出路径
 #include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
  int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
int map[200][200];
int n,m;
struct node
{
 int x,y,t;
 };
node path[200][200];
node road[200];
int l;
node start,target;
int bfs(node start)
{
queue<node> q;
q.push(start);
map[start.x][start.y]=1;
while(!q.empty())
  {
node cur=q.front();
q.pop();
node next;
if(cur.x==1||cur.x==n||cur.y==1||cur.y==m)
{
target.x=cur.x;
target.y=cur.y;
return cur.t;
 }
for(int i=0;i<4;i++)
{
next.x=cur.x+dir[i][0];
next.y=cur.y+dir[i][1];
if(next.x>0&&next.x<=n&&next.y>0&&next.y<=m&&map[next.x][next.y]==0)
{
next.t=cur.t+1;
path[next.x][next.y].x=cur.x;
path[next.x][next.y].y=cur.y;
map[next.x][next.y]=1;
q.push(next);
}
}
}
return -1;
}
void print(int x,int y)
{
if(x==start.x&&y==start.y)
{
road[l].x=x;
road[l++].y=y;
return;
}
print(path[x][y].x,path[x][y].y);
road[l].x=x;
road[l++].y=y;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&map[i][j]);
}
}
int xi,yi;
scanf("%d%d",&xi,&yi);
start.x=xi;
start.y=yi;
start.t=1;
l=1;
int ans=bfs(start);
print(target.x,target.y);
for(i=1;i<l-1;i++)
{
if(road[i+1].x-road[i].x==1&&(road[i+1].y==road[i].y))
printf("D ");
if(road[i+1].x-road[i].x==-1&&(road[i+1].y==road[i].y))
printf("U ");
if(road[i+1].y-road[i].y==1&&(road[i+1].x==road[i].x))
printf("R ");
if(road[i+1].y-road[i].y==-1&&(road[i+1].x==road[i].x))
printf("L ");
}
if(road[l-1].x==n)
printf("D");
if(road[l-1].x==1)
printf("U");
if(road[l-1].y==1)
printf("
#include<stdio.h>
#include<string.h>
int map[50][50];
int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
struct node
{
int x,y;
};
int path[30][2];
int n,m;
int flag=0;
node start;
bool dfs(node start,int step)
{
node cur;
if(step==n*m)
{
flag=1;
return 1;
}
for(int i=0;i<8;i++)
{
cur.x=start.x+dir[i][0];
cur.y=start.y+dir[i][1];
if(cur.x>=1&&cur.x<=m&&cur.y>=1&&cur.y<=n&&map[cur.x][cur.y]==0)
{
map[cur.x][cur.y]=1;
path[step][0]=cur.x+'A'-1;
path[step][1]=cur.y+'0';
dfs(cur,step+1);
if(flag)
return 1;
map[cur.x][cur.y]=0;
}
}
return 0;
}
int main()
{
int t;
scanf("%d",&t);
for(int ii=1;ii<=t;ii++)
{
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
memset(path,0,sizeof(path));
flag=0;
path[0][0]='A';
path[0][1]='1';
start.x=1;
start.y=1;
map[1][1]=1;
printf("Scenario #%d:\n",ii);
if(dfs(start,1))
{
for(int i=0;i<n*m;i++)
{
printf("%c%c",path[i][0],path[i][1]);
}
printf("\n");
}
else
printf("imposs
1 #include<stdio.h>
2 #include<string.h>
3 int map[50][50];
4 int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
5 struct node
6 {
7 int x,y;
8 };
9 int path[30][2];
10 int n,m;
11 int flag=0;
12 node start;
13 bool dfs(node start,int step)
14 {
15 node cur;
16 if(step==n*m)
17 {
18 flag=1;
19 return 1;
20 }
21 for(int i=0;i<8;i++)
22 {
23 cur.x=start.x+dir[i][0];
24 cur.y=start.y+dir[i][1];
25 if(cur.x>=1&&cur.x<=m&&cur.y>=1&&cur.y<=n&&map[cur.x][cur.y]==0)
26 {
27 map[cur.x][cur.y]=1;
28 path[step][0]=cur.x+'A'-1;
29 path[step][1]=cur.y+'0';
30 dfs(cur,step+1);
31 if(flag)
32 return 1;
33 map[cur.x][cur.y]=0;
34 }
35 }
36 return 0;
37 }
38
39 int main()
40 {
41 int t;
42 scanf("%d",&t);
43 for(int ii=1;ii<=t;ii++)
44 {
45 scanf("%d%d",&n,&m);
46 memset(map,0,sizeof(map));
47 memset(path,0,sizeof(path));
48 flag=0;
49 path[0][0]='A';
50 path[0][1]='1';
51 start.x=1;
52 start.y=1;
53 map[1][1]=1;
54 printf("Scenario #%d:\n",ii);
55 if(dfs(start,1))
56 {
57 for(int i=0;i<n*m;i++)
58 {
59 printf("%c%c",path[i][0],path[i][1]);
60 }
61 printf("\n");
62 }
63 else
64 printf("impossible\n");
65 if(ii!=t)
66 printf("\n");
67 }
68 return 0;
69 }
70
71
72
73 ible\n");
if(ii!=t)
printf("\n");
}
return 0;
}
L");
if(road[l-1].y==m)
printf("R");
printf("\n");
}
return 0;
}
POJ 2488 DFS 记录路径 ，每次搜索到就记录，回溯后会更新当前记录的值
|