小清新bfs加各种优化为何 TLE
  • 板块CF225D Snake
  • 楼主Epi4any
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/29 22:31
  • 上次更新2024/7/30 09:01:46
查看原帖
小清新bfs加各种优化为何 TLE
374769
Epi4any楼主2024/7/29 22:31

写的很清楚吧我觉得(?)

vis啥的都搞上了但是TLE6 怎么回事

我表示无法理解

不至于是卡常吧

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,-1,0,1};
const int dy[4]={-1,0,1,0};
const int maxn=25;
struct Node {
    int x, y;
} s,t;
struct _Node {
    int _dist;
    vector<unsigned char> st;
};
int n,m,ans;
char mp[maxn][maxn];
vector<unsigned char> snake;
map<vector<unsigned char>, int> vis;
bool inbound(int x, int y) {
    return x>=1 && x<=n && y>=1 && y<=m;
}
unsigned char gethash(Node pos) {
    return pos.x*16+pos.y;
}
Node getoriginal(unsigned char st) {
    return {(int)st/16,(int)st%16};
}
void init(int x, int y) {
    int cur=mp[x][y]-'0';
//    cout<<(int) gethash({x,y})<<endl;
    snake.push_back(gethash({x,y}));
    for(int dir=0;dir<4;dir++) {
        int px=x+dx[dir],py=y+dy[dir];
        if(inbound(px,py) && mp[px][py]-'0'==cur+1) {
//            cout<<px<<" "<<py<<endl;
            init(px,py);
            return;
        }
    }
}
bool check(vector<unsigned char> s) {
    Node curpos=getoriginal(s[0]);
    for(int i=1;i<s.size();i++) {
        Node originalpos=getoriginal(s[i]);
        if(originalpos.x==curpos.x && originalpos.y==curpos.y) {
            return false;
        }
    }
    return true;
}
queue<_Node> q;
void bfs() {
    q.push({0,snake});
    while(!q.empty()) {
        _Node cur=q.front();
        q.pop();
        if(!vis[cur.st]) {
            vis[cur.st]=1;
            Node curpos=getoriginal(cur.st[0]);
            if(curpos.x==t.x && curpos.y==t.y) {
                ans=cur._dist;
                return;
            }
            for(int dir=0;dir<4;dir++) {
                int px=curpos.x+dx[dir],py=curpos.y+dy[dir];
                vector<unsigned char> tmp={};
                tmp.push_back(gethash({px,py}));
                for(auto it:cur.st) {
                    tmp.push_back(it);
                }
                tmp.pop_back();
                if(inbound(px,py) && mp[px][py]!='#' && check(tmp)) {
                    q.push({cur._dist+1,tmp});
                }
            }
        }
    }
    ans=-1;
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>mp[i][j];
            if(mp[i][j]=='1') {
                s={i,j};
            }
            if(mp[i][j]=='@') {
                t={i,j};
            }
        }
    }
    init(s.x,s.y);
    for(auto it:snake) {
        Node tmp=getoriginal(it);
//        cout<<tmp.x<<" "<<tmp.y<<endl;
    }
    bfs();
    cout<<ans<<endl;
    return 0;
}
2024/7/29 22:31
加载中...