题解 P1300 【城市街道交通费系统】

RedreamMer · 2019-11-15 10:09:04 · 题解

P1300题解

算法： BFS

为什么题解里的人们都是用DFS写的QAQ，一定是我太菜了

这类题目很明显要用搜索做，好像这道题并不会卡 DFS ，但我还是用 BFS 顽强地做了下去

第一步，把数据读入并存储在一张图里，能走标记为 1 ，不能走标记为 0 ，再记录一下起点和终点，注意要标记起点的方向，用优先队列维护，以花费为关键字把最小的放在队首，这部分就做完了

第二步，开始 BFS ，把当前所有能做的步骤都做一遍，即前进、左转、右转、掉头（当前面都不能做时才能做，不然会 WA 一个点），还有，如果当前能做某个步骤，但做了之后不是最优的，那就不要做了，但不做不代表不能做，所以我们要造一个数组来维护当前的最优花费： m[i][j][k] （ i ， j 代表坐标 x ， y ， k 代表方向（k\in[0,3]）），由于有优先队列维护作用，所以先访问到终点就是最快的，直接跳出

第三步，输出 Answer

code：

#include<bits/stdc++.h>
using namespace std;
int a,b,xx,yy,x,y;
int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};//方向数组，很方便 
int m[1001][1001][4];//数组维护花费 
bool s[1001][1001];
char ch;
struct P {//协助优先队列 
    int x,y,to;
    bool operator<(const P& t)const {//优先规则 
        return m[t.x][t.y][t.to]<m[x][y][to];
    }
} k,l;
priority_queue<P> st;
int main() {
    memset(m,0x7f,sizeof m);//初始化 
    cin>>a>>b;
    for(int i=1; i<=a; i++)//读入 
        for(int j=1; j<=b; j++) {
            cin>>ch;
            if(ch!='.') {
                s[i][j]=1;
                if(ch!='#') {
                    if(ch!='F') {
                        if(ch=='N')
                            k.to=0;
                        if(ch=='S')
                            k.to=2;
                        if(ch=='W')
                            k.to=3;
                        if(ch=='E')
                            k.to=1;
                        k.x=i;
                        k.y=j;
                    } else {
                        xx=i;
                        yy=j;
                    }
                }
            }
        }
    m[k.x][k.y][k.to]=0;
    st.push(k);
    while(!st.empty()) {//BFS开始 
        bool q=0;
        k=st.top();
        if(k.x==xx&&k.y==yy)//访问到终点 
        break;
        st.pop();
        x=k.x+dx[k.to];
        y=k.y+dy[k.to];
        if(s[x][y])
            q=1;
        if(s[x][y]&&m[x][y][k.to]>m[k.x][k.y][k.to]) {//前进判断 
            m[x][y][k.to]=m[k.x][k.y][k.to];
            l.x=x;
            l.y=y;
            l.to=k.to;
            st.push(l);
        }
        x=k.x+dx[(k.to+3)%4];
        y=k.y+dy[(k.to+3)%4];
        if(s[x][y])
            q=1;
        if(s[x][y]&&m[x][y][(k.to+3)%4]>m[k.x][k.y][k.to]+1) {//左转判断 
            m[x][y][(k.to+3)%4]=m[k.x][k.y][k.to]+1;
            l.x=x;
            l.y=y;
            l.to=(k.to+3)%4;
            st.push(l);
        }
        x=k.x+dx[(k.to+1)%4];
        y=k.y+dy[(k.to+1)%4];
        if(s[x][y])
            q=1;
        if(s[x][y]&&m[x][y][(k.to+1)%4]>m[k.x][k.y][k.to]+5) {//右转判断 
            m[x][y][(k.to+1)%4]=m[k.x][k.y][k.to]+5;
            l.x=x;
            l.y=y;
            l.to=(k.to+1)%4;
            st.push(l);
        }
        if(!q) {//判断其他操作能不能做 
            x=k.x+dx[(k.to+2)%4];
            y=k.y+dy[(k.to+2)%4];
            if(s[x][y]&&m[x][y][(k.to+2)%4]>m[k.x][k.y][k.to]+10) {//后退判断 
                m[x][y][(k.to+2)%4]=m[k.x][k.y][k.to]+10;
                l.x=x;
                l.y=y;
                l.to=(k.to+2)%4;
                st.push(l);
            }
        }
    }
    cout<<m[k.x][k.y][k.to];
    return 0;
}//97行代码QAQ