Problem H. Jhadgre的回家之路

由 Edwiv 发布于  ｜  50,481次浏览

题目描述 

Jhadgre作为一个热(xiang)爱(dang)学(xian)习(yu)的好同学，每天都在掰着手指头等周末。

今天终于到了周五，等到下午六点他就又可以在寝室做两天咸鱼了。但是Jhadgre上午上完课把钥匙丢在了教室，被Wpremig捡到了，所以他必须先去Wpremig手里取得钥匙才能回寝室。

于是机智的Wpremig为了方便Jhadgre拿钥匙，他去配了好多把Jhadgre的钥匙，分别放在不同的地方 (厉害了小老弟)。

现在Jhadgre想要尽快的回到寝室中，他需要取得任意一把钥匙才能够回寝室，请你帮他计算出回寝室的最短路程。

学校可以背看做是一个n * n的网格，其中一些路有障碍，钥匙和家所在的地方也可以看做是道路，可以通过。Jhadgre可以在任意一条道路中选择上下左右四个方向移动，一次移动算作一步。

输入描述:

多组数据，T<=50,对于每组数据有:
第一行有两个整数n,m。
接下去n行每行m个字符，代表学校地图。
其中, '.'表示道路，'#'表示障碍物，'L'表示Jhadgre所在的位置,'W'表示钥匙的位置，'Q'表示寝室的位置。题目保证最少有一条路可以拿到钥匙并且回到寝室。

输出描述:

Jhadgre回寝室需要走的最少步数。

示例1

输入

8 10
W....#.#W#
..#..#...#
...Q##.#.#
##........
..##.#..##
..........
##..#...##
###..L....

输出

17

题解：写这题的时候不知道在想什么，明明前两天刚刚复习了meet in the meddle算法但是就是没想到；
从L往W搜再从W往Q搜肯定会超时的，最坏的情况下会进行2*n次BFS（n为钥匙数量），所以考虑从两边往中间搜，既先从L开始搜索所有的W，找到后记录到达对应Wi的步数，再从Q往前搜W，最后输出两次BFS加起来的步数的最小值就好了。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0×7ffffff
#define EPS 1e-8
#define maxn 2000+10
#define PI acos(-1.0)
#define pb push_back
using namespace std;
int V[maxn][maxn];
int n,m,ans;
int lstep[maxn][maxn],qstep[maxn][maxn];
int lx,ly,qx,qy,wx[maxn],wy[maxn],pop=0;
char Map[maxn][maxn];
struct pos
{
    int x,y,steps;
};
int check(int x,int y)
{
    if (x<0 || x>=n || y<0 ||y>=m || V[x][y] || Map[x][y]=='#') return 0;
    else return 1;
}
void bfs(int fromx,int fromy,int c)
{
    queue<pos> Q;
    pos cur,nex;
    cur.x=fromx;
    cur.y=fromy;
    cur.steps=0;
    Q.push(cur);
    V[cur.x][cur.y]=1;
    while (!Q.empty())
    {
        cur=Q.front();
        Q.pop();
        if(Map[cur.x][cur.y]=='W'&&c==1)
        {
            lstep[cur.x][cur.y]=cur.steps;
        }
        if(Map[cur.x][cur.y]=='W'&&c==2)
        {
            qstep[cur.x][cur.y]=cur.steps;
        }
        for (int i=1;i!=5;i++)
        {
            if (i==1) {nex.x=cur.x+1;nex.y=cur.y;}
            if (i==2) {nex.x=cur.x-1;nex.y=cur.y;}
            if (i==3) {nex.x=cur.x;nex.y=cur.y+1;}
            if (i==4) {nex.x=cur.x;nex.y=cur.y-1;}
            if (check(nex.x,nex.y))
            {
                nex.steps=cur.steps+1;
                Q.push(nex);
                V[nex.x][nex.y]=1;
            }
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n>>m)
    {
        pop=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                cin>>Map[i][j];
                if(Map[i][j]=='L') {lx=i;ly=j;}
                if(Map[i][j]=='Q') {qx=i;qy=j;}
                if(Map[i][j]=='W') {wx[pop]=i;wy[pop++]=j;}
            }
        ans=maxn*maxn;
        memset(lstep,-1,sizeof(lstep));
        memset(qstep,-1,sizeof(qstep));
        memset(V,0,sizeof(V));
        bfs(lx,ly,1);
        memset(V,0,sizeof(V));
        bfs(qx,qy,2);
        for(int i=0;i<pop;i++)
        {
            if(lstep[wx[i]][wy[i]]!=-1&&qstep[wx[i]][wy[i]]!=-1)
            {
                ans=min(ans,lstep[wx[i]][wy[i]]+qstep[wx[i]][wy[i]]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

以下为标程（真是值得学习的写法）

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2010;
const int INF = 0x3f3f3f3f;
int n, m;
int vis[MAXN][MAXN];
int ret[2][MAXN][MAXN];
char a[MAXN][MAXN];
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
void bfs(int xxx, int yyy, int d) {
queue< pair<int, int> > q;
q.push(make_pair(xxx, yyy));
vis[xxx][yyy] = 1;
ret[d][xxx][yyy] = 0;
while(!q.empty()) {
int tx = q.front().first;
int ty = q.front().second;
q.pop();
for (int i = 0;i < 4; ++i) {
int x = tx + xx[i];
int y = ty + yy[i];
if (x >= 0 && x < n && y >= 0 && y < m && a[x][y] != '#' && !vis[x][y]) {
ret[d][x][y] = ret[d][tx][ty] + 1;
vis[x][y] = 1;
q.push(make_pair(x, y));
}
}
}
}
int main() {
while (~scanf("%d %d", &n, &m)){
queue< pair<int, int> > q;
memset(ret, INF, sizeof(ret));
memset(vis, 0, sizeof(vis));
int sx, sy;
int tx, ty;
for (int i = 0;i < n; ++i) {
scanf("%s", a[i]);
for (int j = 0;j < m; ++j) {
if (a[i][j] == 'W') {
q.push(make_pair(i, j));
} else if (a[i][j] == 'L') {
sx = i;
sy = j;
} else if (a[i][j] == 'Q') {
tx = i;
ty = j;
}
}
}
bfs(sx, sy, 0);
memset(vis, 0, sizeof(vis));
bfs(tx, ty, 1);
int ans = INF;
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
ans = min(ans, ret[0][x][y] + ret[1][x][y]);
}
printf("%d\n", ans);
}
return 0;
}

 

附上错误示范（比赛时提交的代码）

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <string.h>
#include <vector>
#include <iterator>
#include <map>
#include <set>
#include <cmath>
#include <stdio.h>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define EPS 1e-8
#define maxn 2010+10
#define PI acos(-1.0)
using namespace std;
int V[maxn][maxn];
int n,m,ans,ans1,ans2;
int lx,ly,qx,qy,wx[maxn],wy[maxn],pop=0;
char Map[maxn][maxn];
struct pos
{
    int x,y,steps;
};
int check(int x,int y)
{
    if (x<0 || x>=n || y<0 ||y>=m || V[x][y] || Map[x][y]=='#') return 0;
    else return 1;
}
int bfs1(int fromx,int fromy,int tox,int toy)
{
    queue<pos> Q;
    pos cur,nex;
    cur.x=fromx;
    cur.y=fromy;
    cur.steps=0;
    Q.push(cur);
    V[cur.x][cur.y]=1;
    while (!Q.empty())
    {
        cur=Q.front();
        Q.pop();
        if (cur.x==tox&&cur.y==toy)
        {
            return cur.steps;
        }
        for (int i=1;i!=5;i++)
        {
            if (i==1) {nex.x=cur.x+1;nex.y=cur.y;}
            if (i==2) {nex.x=cur.x-1;nex.y=cur.y;}
            if (i==3) {nex.x=cur.x;nex.y=cur.y+1;}
            if (i==4) {nex.x=cur.x;nex.y=cur.y-1;}
            if (check(nex.x,nex.y))
            {
                nex.steps=cur.steps+1;
                if (nex.steps>=ans1) break;
                Q.push(nex);
                V[nex.x][nex.y]=1;
            }
        }
    }
    return -1;
}
int bfs2(int fromx,int fromy,int tox,int toy)
{
    queue<pos> Q;
    pos cur,nex;
    cur.x=fromx;
    cur.y=fromy;
    cur.steps=0;
    Q.push(cur);
    V[cur.x][cur.y]=1;
    while (!Q.empty())
    {
        cur=Q.front();
        Q.pop();
        if (cur.x==tox&&cur.y==toy)
        {
            return cur.steps;
        }
        for (int i=1;i!=5;i++)
        {
            if (i==1) {nex.x=cur.x+1;nex.y=cur.y;}
            if (i==2) {nex.x=cur.x-1;nex.y=cur.y;}
            if (i==3) {nex.x=cur.x;nex.y=cur.y+1;}
            if (i==4) {nex.x=cur.x;nex.y=cur.y-1;}
            if (check(nex.x,nex.y))
            {
                nex.steps=cur.steps+1;
                if (nex.steps>=ans-ans1) break;
                Q.push(nex);
                V[nex.x][nex.y]=1;
            }
        }
    }
    return -1;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n>>m)
    {
        pop=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                {
                    cin>>Map[i][j];
                    if(Map[i][j]=='L') {lx=i;ly=j;}
                    if(Map[i][j]=='Q') {qx=i;qy=j;}
                    if(Map[i][j]=='W') {wx[pop]=i;wy[pop++]=j;}
                }
        ans=maxn*maxn;
        ans1=maxn*maxn;
        ans2=maxn*maxn;
        for(int i=0;i<pop;i++)
        {
            memset(V,0,sizeof(V));
            ans1=bfs1(lx,ly,wx[i],wy[i]);
            //cout<<ans1<<endl;
            if(ans1<ans&&ans1!=-1)
            {
                memset(V,0,sizeof(V));
                ans2=bfs2(wx[i],wy[i],qx,qy);
                if(ans2!=-1)
                    ans=min(ans,ans1+ans2);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

订阅评论
提醒
0 评论
内联反馈
查看所有评论