201604-4 ccf 游戏（三维记录 + BFS）

谁践踏了优雅 2022-05-14 09:51 215阅读 0赞

题目链接：  
[游戏][Link 1]

题目大意：  
中文题啊！！！

解题思路：  
真的是让我学到了的一题！！！  
一开始看到题，二话不说上了普通的无访问标记式的bfs,结果TLE了，只得了20分，想想确实会超时。  
于是想了一些剪枝方法，还是不行。因为突然发现好像还可能需要走回去，才会有最优解。于是冥思苦想，无果。决定上网看看各路神仙写法！！！  
找到一个觉得想法特别清奇的，就是用思维数组标记访问，比普通vis多出来一个时间维度。  
那么我们把在时间a~b这段时间的vis\[r\]\[c\]\[t\]标记为1，访问过的标记，第一次遇到终点，退出bfs，就是答案了。

因为a,b取值最大为100，网格也最多100\*100，所以最短到达终点只需300步这样  
所以最坏的时间复杂度是O(300\*n\*m)

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <queue>
    
    using namespace std;
    
    int n,m,t;
    int vis[150][150][350];
    
    struct node{
        int x,y,time;
        node(int _x, int _y,int _t):x(_x),y(_y),time(_t){}
    };
    
    int dir[4][2] = {
       {-1,0},{
       1,0},{
       0,-1},{
       0,1}};
    
    int bfs(){
        queue<node> q;
        q.push(node(1,1,0));
        vis[1][1][0] = 1;
        while(!q.empty()){
            node tmp = q.front();
            q.pop();
            int tt = tmp.time + 1;
            for(int i=0; i<4; ++i){
                int tx = tmp.x + dir[i][0];
                int ty = tmp.y + dir[i][1];
                if(tx == n && ty == m){
                    return tt;
                }
                if(vis[tx][ty][tt] || tx <=0 || tx >n || ty <=0 || ty >m) continue;
                vis[tx][ty][tt] = 1;
                q.push(node(tx,ty,tt));
            }
        }
    }
    
    int main(){
        memset(vis, 0, sizeof(vis));
        cin>>n>>m>>t;
        while(t--){
            int r,c,a,b;
            cin>>r>>c>>a>>b;
            for(int i=a; i<=b; ++i) vis[r][c][i] = 1;
        }
    
        cout<<bfs()<<endl;
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T39