\(H,W \leq 50\) と小さい． 盤面は，(人の座標，荷物の座標) さえ分かっていれば，後は何とかなる．
実装
(人の座標，荷物の座標)を持ちながらBFS. グラフの頂点の個数は \(O(\ (H \times W)^{2}\ )\), 辺の個数は，頂点の4倍． よって，合計で \(O(5(H \times W)^{2})\) より， \(3.125 \cdot 10^{7}\) 程度．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll dis[55][55][55][55];
bool vis[55][55][55][55];
int main() {
ll h,w; cin >> h >> w;
cinv(s);
rep(x,h) rep(y,w) rep(a,h) rep(b,w){
dis[x][y][a][b] = INFL;
}
// remark : s[x][y] != 'a' は不要
auto valid = [&](ll x, ll y) -> bool {
return in(x,h) && in(y,w) && (s[x][y]!='#');
};
using T = tuple<ll,ll,ll,ll>;
queue<T> que;
auto push = [&](ll x, ll y, ll a, ll b, ll d) -> void {
// if(!valid(x,y)) return; // rem : valid のタイミング
if(vis[x][y][a][b]) return;
vis[x][y][a][b] = true;
que.push({x,y,a,b});
dis[x][y][a][b] = d;
};
pll src, tar, car; // cargo
rep(x,h) rep(y,w){
if(s[x][y] == 's') src.first = x, src.second = y;
if(s[x][y] == 'g') tar.first = x, tar.second = y;
if(s[x][y] == 'a') car.first = x, car.second = y;
}
push(src.first, src.second, car.first, car.second, 0);
while(que.size()){
auto [x,y,a,b] = que.front(); que.pop();
ll d = dis[x][y][a][b];
vll dx = {-1,0,1,0};
vll dy = {0,-1,0,1};
rep(i,4){
ll nx = x + dx[i];
ll ny = y + dy[i];
pll px = {nx, ny};
if(valid(nx,ny)) push(nx, ny, a, b, d+1);
}else{
// 2マス先
ll nx2 = x + 2*dx[i];
ll ny2 = y + 2*dy[i];
if(valid(nx2, ny2)) push(nx, ny, nx2, ny2, d+1);
}
}
}
ll ans = INFL;
rep(x,h) rep(y,w){
chmin(ans, dis[x][y][tar.first][tar.second]);
}
if(ans >= INFL) cout << -1 << endl;
else cout << ans << endl;
return 0;
}
