POJ 3083 -- Children of the Candy Corn（DFS+BFS）
题意:
给定一个迷宫，S是起点，E是终点，#是墙不可走，.可以走
1）先输出左转优先时，从S到E的步数
2）再输出右转优先时，从S到E的步数
3）最后输出S到E的最短步数
解题思路：
前两问DFS，转向只要控制一下旋转方向就可以
首先设置前进方向对应的数字
向上——N——0
向右——E——1
向下——S——2
向左——W——3
比如说右转优先，即为向右，向前，向左，向后，即逆时针方向for(int i=1;i>=-2;i--)
左转优先，即为向左，向前，向右，向后，即顺时针方向for(int i=-1;i<=3;i++)
第三问最短路，BFS
普通递归（TLE）
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int r,c;///行r，列c
int r0,c0,r3,c3;///r0,c0用来标记入口，r3,c3用来标记出口
const char *dirs = "NESW";
const int maxn = ;
char square[maxn][maxn];
const int dr[] = {-,,,};
const int dc[] = { ,,,-};
struct node{
int row,col,deep;
int dir;///0123对应NESW
node(int row=,int col=,int dir=,int deep=):row(row),col(col),dir(dir),deep(deep){}
};
bool inside(int xx,int yy)
{
return xx>= && xx<=r && yy>= && yy<=c;
} bool flag1;
int step1;
void dfs1(node *way,int x,int y,int d,int step)
{///左转优先
way[step].row = x;
way[step].col = y;
way[step].dir = d;
if(x==r3 && y==c3)///走到出口
{
step1 = step;
flag1 = true;
return;
}
for(int i=-;i<=;i++)
{
int tempDir = (way[step].dir + + i)%;///进行旋转
int xx = way[step].row + dr[tempDir];
int yy = way[step].col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界，可以行走
dfs1(way,xx,yy,tempDir,step+);
}
if(flag1)
return;
}
return;
} int step2;bool flag2;
void dfs2(node *way,int x,int y,int d,int step)
{///右转优先
way[step].row = x;
way[step].col = y;
way[step].dir = d;
if(x==r3 && y==c3)///走到出口
{
step2 = step;
flag2 = true;
return;
}
for(int i=;i>=-;i--)
{
int tempDir = (way[step].dir + + i)%;///进行旋转
int xx = way[step].row + dr[tempDir];
int yy = way[step].col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界，可以行走
dfs2(way,xx,yy,tempDir,step+);
}
if(flag2)
return;
}
return;
}
node d[maxn][maxn][]; void bfs(int x,int y,int d)
{
queue<node> q;
node u(x,y,d,);///入口结点
q.push(u);
while(!q.empty())
{
node u = q.front();q.pop();
if(u.row == r3 && u.col == c3)
{
cout<<u.deep<<endl;
return;
}
for(int i=;i<=;i++)
{
int tempDir = (u.dir +i)%;///进行旋转
int xx = u.row + dr[tempDir];
int yy = u.col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界，可以行走
node v(xx,yy,tempDir,u.deep+);
q.push(v);
}
}
}
} int startDir()
{///计算从入口进入之后的方向
if(r0 == ) return ;
else if(r0 == r) return ;
else if(c0 == ) return ;
else return ;
}
int main()
{
int n;
cin>>n;
while(n--)
{
cin>>c>>r;///输入为先输入列数，在输入行数
char temp;
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
{
temp = getchar();
while(temp == '\n') temp = getchar();
square[i][j] = temp;
if(temp == 'S'){r0 = i;c0 = j;}
if(temp == 'E'){r3 = i;c3 = j;}
}
node *way = new node[maxn*maxn];
///求解左转优先
flag1 = false;step1 = ;
int startdir = startDir();
dfs1(way,r0,c0,startdir,);
if(flag1) cout<<step1<<" ";
///求解右转优先
flag2 = false;step2 = ;
dfs2(way,r0,c0,startdir,);
if(flag2) cout<<step2<<" ";
///求解最短路径
bfs(r0,c0,startdir);
}
return ;
}
最终成功代码
Time Limit Exceeded原因：POJ对STL兼容性不高，使用queue超时
其次，DFS使用尾递归形式，遇到可行解，直接向下一层搜索
最后，BFS不能走重复路线，否则会陷入死循环，Runtime Error
仅此告诫自己
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int r,c;///行r，列c
int r0,c0,r3,c3;///r0,c0用来标记入口，r3,c3用来标记出口 const int maxn = ;
char square[maxn][maxn];
const int dr[] = {-,,,};
const int dc[] = { ,,,-}; struct node{
int row,col,deep;
int dir;///0123对应NESW
node(int row=,int col=,int dir=,int deep=):row(row),col(col),dir(dir),deep(deep){}
};
bool inside(int xx,int yy)
{
return xx>= && xx<=r && yy>= && yy<=c;
}
int dfs12(int x,int y,int d)
{///左转优先
if(square[x][y] == 'E')
return ;
int tempDir,xx,yy;
for(int i=-;i<=;i++)
{
tempDir = (d + + i)%;///进行旋转
xx = x + dr[tempDir];
yy = y + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界，可以行走
break;
}
}
return dfs12(xx,yy,tempDir)+;
}
int dfs22(int x,int y,int d)
{///you转优先
if(square[x][y] == 'E')
return ;
int tempDir,xx,yy; for(int i=;i>=-;i--)
{
tempDir = (d + + i)%;///进行旋转
xx = x + dr[tempDir];
yy = y + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#')
{///没有出界，可以行走
break;
}
}
return dfs22(xx,yy,tempDir)+;
} node queue[];
bool has_walk[maxn][maxn];
void bfs(int x,int y,int d)
{
int head=,tail=;
node u(x,y,d,);
has_walk[x][y] = false;
queue[head] = u;///入口结点
while(head<tail)
{
node u = queue[head++];
if(u.row == r3 && u.col == c3)
{
cout<<u.deep<<endl;
return;
}
for(int i=;i<=;i++)
{
int tempDir = (u.dir +i)%;///进行旋转
int xx = u.row + dr[tempDir];
int yy = u.col + dc[tempDir];
if(inside(xx,yy) && square[xx][yy]!='#' && has_walk[xx][yy])
{///没有出界，可以行走，没有走过true
node v(xx,yy,tempDir,u.deep+);
has_walk[xx][yy] = false;
queue[tail] = v;
tail++;
}
}
}
} int startDir()
{///计算从入口进入之后的方向
if(r0 == ) return ;
else if(r0 == r) return ;
else if(c0 == ) return ;
else return ;
}
int main()
{
int n;
while(cin>>n)
while(n--)
{
cin>>c>>r;///输入为先输入列数，在输入行数
memset(has_walk,true,sizeof(has_walk));///true表示当前格子没有走过，可以走
char temp;
for(int i=;i<=r;i++)
for(int j=;j<=c;j++)
{
temp = getchar();
while(temp == '\n') temp = getchar();
square[i][j] = temp;
if(temp == 'S'){r0 = i;c0 = j;}
if(temp == 'E'){r3 = i;c3 = j;}
}
///求解左转优先
int startdir = startDir();
cout<<dfs12(r0,c0,startdir)<<" ";
///求解右转优先
cout<<dfs22(r0,c0,startdir)<<" ";
///求解最短路径
bfs(r0,c0,startdir);
}
return ;
}
最后给大家提供点测试样例：
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E#### #########
#.#.#.#.#
S.......E
#.#.#.#.#
######### ########
#.#.#..#
S......E
#.#.#..#
######## ##
SE
## ######E#
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S######
结果：