bfs 的问题？扩展的时候得判断一下是否扩展过了（vis 数组）。
by lnwhl @ 2023-05-19 16:37:34
为什么比题解快，还T了？
by Acoipp @ 2023-05-19 16:37:42
@[dlsk_po](/user/674469) 楼主的意思可能是跑样例更快，而且题解写的都比较劣（状压了 20 个点）
by lnwhl @ 2023-05-19 16:42:20
我扩展的时候判断过了啊
`if(vis[vx][vy]||vx<1||vx>n||vy<1||vy>m||s[vx][vy]=='#'||ulen+1>t) continue;`
这一行第一个就是..
by jr_zch @ 2023-05-19 17:09:12
确实就是样例跑得快很多
by jr_zch @ 2023-05-19 17:09:38
@[jr_zch](/user/772999) 状压的时候还能优化，有些点之间走不通，不用计算。
by Lien @ 2023-05-20 19:19:11
我写的普通状压+BFS过了
by Acoipp @ 2023-05-20 21:46:57
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,t,i,j,k,tot=1,tx,ty,x[305],y[305],lon[25][25],dd[305][305];
char maps[305][305];
ll dp[1<<21][21],px[4]={0,0,1,-1},py[4]={1,-1,0,0},ans=LLONG_MIN;
deque<pair<ll,ll> > op;
void bfs(ll xx,ll yy,ll id){
memset(dd,0x3f,sizeof(dd));
dd[xx][yy] = 0;
op.push_back(make_pair(xx,yy));
while(op.size()){
tx = op.front().first,ty = op.front().second;
op.pop_front();
for(ll i=0;i<4;i++){
ll lx = tx+px[i],ly = ty+py[i];
if(lx<1||lx>n||ly<1||ly>m||maps[lx][ly]=='#') continue;
if(dd[lx][ly]>dd[tx][ty]+1){
dd[lx][ly] = dd[tx][ty]+1;
op.push_back(make_pair(lx,ly));
}
}
}
for(ll i=1;i<=tot;i++) lon[id][i] = dd[x[i]][y[i]];
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>t;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin>>maps[i][j];
if(maps[i][j]=='o'){
tot++;
x[tot] = i,y[tot] = j;
}
if(maps[i][j]=='S') x[1]=i,y[1]=j;
if(maps[i][j]=='G') tx=i,ty=j;
}
}
tot++,x[tot]=tx,y[tot]=ty;
for(i=1;i<=tot;i++) bfs(x[i],y[i],i);
memset(dp,0x3f,sizeof(dp));
dp[1<<0][1] = 0;
for(i=2;i<(1<<tot);i++){
for(j=1;j<=tot;j++){
if((i>>(j-1))&1){
for(k=1;k<=tot;k++){
if(j!=k&&((i>>(k-1))&1)){
dp[i][j] = min(dp[i][j],dp[i-(1<<(j-1))][k]+lon[k][j]);
}
}
}
}
}
for(i=1;i<(1<<tot);i++){
if(i%2==1&&((i>>(tot-1))&1)){
if(dp[i][tot]<=t){
k = i;
ll cnt = 0;
while(k) cnt+=k%2,k/=2;
ans = max(ans,cnt-2);
}
}
}
if(ans!=LLONG_MIN) cout<<ans<<endl;
else cout<<"-1\n";
}
/*
3 3 3
SG.
o..
...
*/
```
by Acoipp @ 2023-05-20 21:47:27
过掉了，问题在于我的 `bfs` 只判断了扩展出去的点的 $vis$ 没有判断原点。。
低级错误了。。
by jr_zch @ 2023-05-20 21:49:18