dlut1188(wanghang的迷宫)

题目大意:从起点到终点需要最少多少步(必须要关掉所有开关才能出去)

题目思路:用一个3维数组 dp[x][y][t]表示到达当前位置x，y，已经关掉了t个开关走的最少步数，然后就是bfs搜索

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 1000010
#define maxn 400005
typedef pair<int,int> PII;
 
int n,m,sx,sy;
char pic[15][15];
int dp[15][15][5];     ///记录在关掉t个开关的情况下走到当前位置用得最少步数
int dir[][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node{
    int x,y,t,v;       ///v记录步数,t记录关掉的开关数目
    int vi[5];         ///判断当前状态哪些开关已经关掉了
    void ini(){mst(vi,0);v=t=0;}
}node,temp;
void bfs(){
    mst(dp,inf);
    dp[node.x][node.y][0]=0;
    queue<Node>q;q.push(node);
    while(!q.empty()){
        node=q.front();q.pop();
        if(pic[node.x][node.y]=='E'){
            if(node.t==9){
                dp[node.x][node.y][9]=min(dp[node.x][node.y][9],node.v);
            }
            continue;
        }
        for(int i=0;i<4;++i){
            int xx=node.x+dir[i][0];
            int yy=node.y+dir[i][1];
            if(xx<1||yy<1||xx>n||yy>m||pic[xx][yy]=='#')continue;
            temp=node;temp.x=xx;temp.y=yy;
            temp.v++;
            if(pic[xx][yy]=='A'&&!temp.vi[0]){
                temp.vi[0]=1;
                temp.t++;
            }
            else if(pic[xx][yy]=='B'&&!temp.vi[1]){
                temp.vi[1]=1;
                temp.t++;
            }
            else if(pic[xx][yy]=='C'&&!temp.vi[2]){
                temp.vi[2]=1;
                temp.t++;
            }
            if(dp[xx][yy][node.t]>temp.v){
                dp[xx][yy][node.t]=temp.v;
                q.push(temp);
            }
        }
    }
    if(dp[sx][sy][3]<inf)
    printf("%d
",dp[sx][sy][3]);
    else printf("-1
");
}
int main(){
    int i,j,group,Case=0;
    scanf("%d",&group);
    while(group--){
        node.ini();
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;++i){
            scanf("%s",pic[i]+1);
            for(j=1;j<=m;++j){
                if(pic[i][j]=='S'){node.x=i;node.y=j;}
                else if(pic[i][j]=='E'){sx=i;sy=j;}
            }
        }
        bfs();
    }
    return 0;
}

dlut1188(wanghang的迷宫)

相关推荐