带方向限制的bfs

题目传送门

大致思路

求最短路径,想到bfs,但是带有方向限制,可以在队列中加入一些"标签"来限制
同时要注意vis数组并不能只有二维,因为可能不同方向来到同一个位置产生的答案是不一样的,不能到了一次之后,就不再去了,用三维来加一个方向标签

Code

void solve() {
    int m,n;
    cin>>m>>n;
    vector<vector<int> > a(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    queue<vector<int> > q;
    q.push({1,1,9,0});
    vector<vector<vector<bool>> > vis(10,vector<vector<bool>>(n+1,vector<bool>(m+1)));
    vis[9][1][1]=true;
    while(!q.empty()) {
        auto t = q.front();
        q.pop();
        int x=t[0],y=t[1];
        int s=t[2],step=t[3],path=a[x][y];
        if (x==n && y==m) {
            cout<<step<<el;
            return;
        }
        for (int i=0;i<8;i++) {
            int nx= x+dx[i]*path;
            int ny= y+dy[i]*path;
            if (s==i)continue;
            if (nx>=1 && nx<=n && ny>=1 && ny<=m && vis[i][nx][ny]==false) {
                vis[i][nx][ny]=true;
                q.push({nx,ny,i,step+1});
            }
        }
    }
    cout<<"NEVER"<<el;
}