写的很清楚吧我觉得(?)
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;
}