HDU/HDOJ 2102 A计划广度优先搜索BFS - c++编程基础

wa了很多次，很悲剧，传送门有几个需要注意的细节，看remap函数，对这些情况的处理。

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,t,flag;
int dir[4][2]={-1,0,1,0,0,1,0,-1};
char maze[2][11][11];
bool visit[2][11][11];
struct node{
int x,y,h;
int step;
}p,q,endp;
queue Q;
bool isbond(node &a){
if(a.x<0||a.x>=m||a.y<0||a.y>=n)return 1;
return 0;
}
void bfs()
{
while(!Q.empty())Q.pop();

p.x=p.y=p.h=p.step=0;
visit[0][0][0]=1;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();

if(maze[p.h][p.x][p.y]=='#'){ //传送
if(!visit[!p.h][p.x][p.y]){
if(maze[!p.h][p.x][p.y]=='P'){
if(p.step<=t){
flag=1;
return ;
}
return ;
}
visit[!p.h][p.x][p.y]=1;
p.h=!p.h;
Q.push(p);
}

continue;
}
for(int i=0;i<4;i++)
{
q.x=p.x+dir[i][0];
q.y=p.y+dir[i][1];
q.h=p.h;
q.step=p.step+1;

if(isbond(q))continue; // 边界
if(maze[q.h][q.x][q.y]=='*')continue; //当前障碍
if(visit[q.h][q.x][q.y])continue; //访问
if(maze[q.h][q.x][q.y]=='P'){
if(q.step<=t){
flag=1;
return ;
}
return ;
}
visit[q.h][q.x][q.y]=1;
Q.push(q);
}
}
}
void remap()
{
for(int i=0;i {
for(int j=0;j {
if((maze[0][i][j]=='#'&&maze[1][i][j]=='#')||(maze[0][i][j]=='#'&&maze[1][i][j]=='*')||(maze[0][i][j]=='*'&&maze[1][i][j]=='#'))
maze[0][i][j]=maze[1][i][j]='*';
}
}
}
int main()
{
int c;
// ifstream fin;
// fin.open("aaa.txt");

cin>>c;
while(c--)
{
cin>>n>>m>>t;
for(int i=0;i for(int j=0;j cin>>maze[0][i][j];
}
for(int i=0;i for(int j=0;j cin>>maze[1][i][j];
}
flag=0;
memset(visit,0,sizeof(visit));
remap();
bfs();
if(flag)cout<<"YES"< else cout<<"NO"<
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,t,flag;
int dir[4][2]={-1,0,1,0,0,1,0,-1};
char maze[2][11][11];
bool visit[2][11][11];
struct node{
int x,y,h;
int step;
}p,q,endp;
queue Q;
bool isbond(node &a){
if(a.x<0||a.x>=m||a.y<0||a.y>=n)return 1;
return 0;
}
void bfs()
{
while(!Q.empty())Q.pop();

p.x=p.y=p.h=p.step=0;
visit[0][0][0]=1;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();

if(maze[p.h][p.x][p.y]=='#'){ //传送
if(!visit[!p.h][p.x][p.y]){
if(maze[!p.h][p.x][p.y]=='P'){
if(p.step<=t){
flag=1;
return ;
}
return ;
}
visit[!p.h][p.x][p.y]=1;
p.h=!p.h;
Q.push(p);
}

continue;
}
for(int i=0;i<4;i++)
{
q.x=p.x+dir[i][0];
q.y=p.y+dir[i][

HDU/HDOJ 2102 A计划 广度优先搜索BFS (一)

HDU/HDOJ 2102 A计划广度优先搜索BFS (一)