搜索专题: HDU2102 A计划

这不知道是公主被抓走了第几次了，反正我们的骑士救就对了（别说了，我都救我都救...）;这次的迷宫有些特别，双层，带电梯（？），而且这个电梯还有生命危险，可能会撞死（一层是电梯，一层是墙），或者永远困在电梯里（上下两层都是电梯），而且上了电梯必须移动，我想到的是BFS，WA了一次，主要是这题的细节问题比较多，认真处理一下就好；

代码如下:

Problem : 2102 ( A计划 )     Judge Status : Accepted
RunId : 21313702    Language : C++    Author : hnustwanghe
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta

#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int N = 10 + 5; const int INF = (1<<30); char mat[2][N][N]; bool visit[2][N][N]; typedef struct node{ int x,y,z,val; node(int x=0,int y=0,int z=0,int val=0):x(x),y(y),z(z),val(val){} }Node; Node goal; int n,m,k; const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; bool BFS(){ queue<Node> Q; int ans = INF; Node t,s; Q.push(Node(0,0,0)); visit[0][0][0] = true; while(!Q.empty()){ t = Q.front();Q.pop(); if(t.x==goal.x && t.y == goal.y && t.z == goal.z && t.val<=k) { ans=min(ans,t.val);continue;} for(int d=0;d<4;d++){ int newx = t.x + dir[d][0]; int newy = t.y + dir[d][1]; if(newx >= 0 && newx < n && newy >=0 && newy < m && !visit[t.z][newx][newy] && mat[t.z][newx][newy]!='*'){ if(mat[t.z][newx][newy]=='#' && !visit[t.z^1][newx][newy]){ s.x =newx,s.y= newy ,s.val = t.val+1,s.z = t.z^1; visit[t.z^1][newx][newy] = visit[t.z][newx][newy] = true; Q.push(s); }else{ s.x = newx , s.y = newy,s.val = t.val+1,s.z = t.z; visit[t.z][newx][newy] = true; //if(t.val <= k) Q.push(s); } } } } return ans!=INF; } void solve_question(){ memset(visit,0,sizeof(visit)); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ if(mat[0][i][j]=='*' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*'; if(mat[0][i][j]=='#' && mat[1][i][j]=='*') mat[0][i][j] = mat[1][i][j] = '*'; if(mat[0][i][j]=='#' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*'; } printf("%s\n",BFS()?"YES":"NO"); } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d %d %d",&n,&m,&k); for(int k=0;k<2;k++) for(int i=0;i<n;i++){ scanf("%s",mat[k][i]); for(int j=0;j<m;j++) if(mat[k][i][j]=='P') goal.x = i,goal.y = j,goal.z = k; } solve_question(); } return 0; }

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

using namespace std;
const int N = 10 + 5;
const int INF = (1<<30);
char mat[2][N][N];
bool visit[2][N][N];
typedef struct node{
    int x,y,z,val;
    node(int x=0,int y=0,int z=0,int val=0):x(x),y(y),z(z),val(val){}
}Node;
Node goal;
int n,m,k;
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool BFS(){
    queue<Node> Q;
    int ans = INF;
    Node t,s;
    Q.push(Node(0,0,0));
    visit[0][0][0] = true;
    while(!Q.empty()){
        t = Q.front();Q.pop();
        if(t.x==goal.x && t.y == goal.y && t.z == goal.z && t.val<=k) { ans=min(ans,t.val);continue;}
        for(int d=0;d<4;d++){
            int newx = t.x + dir[d][0];
            int newy = t.y + dir[d][1];
            if(newx >= 0 && newx < n && newy >=0 && newy < m  && !visit[t.z][newx][newy] && mat[t.z][newx][newy]!='*'){
                if(mat[t.z][newx][newy]=='#' && !visit[t.z^1][newx][newy]){
                    s.x =newx,s.y= newy ,s.val = t.val+1,s.z = t.z^1;
                    visit[t.z^1][newx][newy] = visit[t.z][newx][newy] = true;
                    Q.push(s);
                }else{
                    s.x = newx , s.y = newy,s.val = t.val+1,s.z = t.z;
                    visit[t.z][newx][newy] = true;
                    //if(t.val <= k)
                    Q.push(s);
                }
            }
        }
    }
    return ans!=INF;
}
void solve_question(){
    memset(visit,0,sizeof(visit));
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++){
        if(mat[0][i][j]=='*' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*';
        if(mat[0][i][j]=='#' && mat[1][i][j]=='*') mat[0][i][j] = mat[1][i][j] = '*';
        if(mat[0][i][j]=='#' && mat[1][i][j]=='#') mat[0][i][j] = mat[1][i][j] = '*';
    }
    printf("%s\n",BFS()?"YES":"NO");
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&n,&m,&k);
        for(int k=0;k<2;k++)
        for(int i=0;i<n;i++){
            scanf("%s",mat[k][i]);
            for(int j=0;j<m;j++)
                if(mat[k][i][j]=='P') goal.x = i,goal.y = j,goal.z = k;
        }
        solve_question();
    }
    return 0;
}