#include "bits/stdc++.h"
using namespace std;

int n,m,bx,by,sx,sy,tx,ty;
vector<vector<char>> a;
map <pair <pair <int,int>,pair <int,int>>,int> dp;

int dx[]={+1,-1, 0, 0};
int dy[]={ 0, 0,+1,-1};

bool invalid(int x,int y)
{
	return min(x,y)<0 or x>=n or y>=m or a[x][y]=='#';
}

void add(int bx,int by,int sx,int sy,queue <pair <pair <int,int>,pair <int,int>>> &q,int dist)
{
	if(invalid(bx,by) or invalid(sx,sy) or dp.find({{bx,by},{sx,sy}})!=dp.end()) return;
	q.push({{bx,by},{sx,sy}});
	dp[{{bx,by},{sx,sy}}]=dist;
}

class Solution
{
public:
	int minPushBox(vector<vector<char>>& grid)
	{
		a=grid;
		dp.clear();
		n=a.size(),m=a[0].size();
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				if(a[i][j]=='B') bx=i,by=j;
				else if(a[i][j]=='S') sx=i,sy=j;
				else if(a[i][j]=='T') tx=i,ty=j;

		queue <pair <pair <int,int>,pair <int,int>>> cur;
		add(bx,by,sx,sy,cur,0);
		while(not cur.empty())
		{
			queue <pair <pair <int,int>,pair <int,int>>> nxt;
			while(not cur.empty())
			{
				auto pp=cur.front();
				cur.pop();

				int dist=dp[pp];
				auto box=pp.first;
				auto shopkeeper=pp.second;
				if(box.first==tx and box.second==ty) return dist;

				for(int k=0;k<4;k++)
				{
					int nsx=shopkeeper.first+dx[k],nsy=shopkeeper.second+dy[k];
					if(invalid(nsx,nsy)) continue;
					if(nsx==box.first and nsy==box.second)
					{
						if(invalid(box.first+dx[k],box.second+dy[k])) continue;
						add(box.first+dx[k],box.second+dy[k],nsx,nsy,nxt,dist+1);
					}
					else add(box.first,box.second,nsx,nsy,cur,dist);
				}
			}
			cur=nxt;
		}

		return -1;
	}
};

#ifdef LOCAL
int main()
{
	vector <int> v={1,2};
	auto ans=Solution().maxSumDivThree(v);
}
#endif

I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbixtLGJ4LGJ5LHN4LHN5LHR4LHR5Owp2ZWN0b3I8dmVjdG9yPGNoYXI+PiBhOwptYXAgPHBhaXIgPHBhaXIgPGludCxpbnQ+LHBhaXIgPGludCxpbnQ+PixpbnQ+IGRwOwoKaW50IGR4W109eysxLC0xLCAwLCAwfTsKaW50IGR5W109eyAwLCAwLCsxLC0xfTsKCmJvb2wgaW52YWxpZChpbnQgeCxpbnQgeSkKewoJcmV0dXJuIG1pbih4LHkpPDAgb3IgeD49biBvciB5Pj1tIG9yIGFbeF1beV09PScjJzsKfQoKdm9pZCBhZGQoaW50IGJ4LGludCBieSxpbnQgc3gsaW50IHN5LHF1ZXVlIDxwYWlyIDxwYWlyIDxpbnQsaW50PixwYWlyIDxpbnQsaW50Pj4+ICZxLGludCBkaXN0KQp7CglpZihpbnZhbGlkKGJ4LGJ5KSBvciBpbnZhbGlkKHN4LHN5KSBvciBkcC5maW5kKHt7YngsYnl9LHtzeCxzeX19KSE9ZHAuZW5kKCkpIHJldHVybjsKCXEucHVzaCh7e2J4LGJ5fSx7c3gsc3l9fSk7CglkcFt7e2J4LGJ5fSx7c3gsc3l9fV09ZGlzdDsKfQoKY2xhc3MgU29sdXRpb24KewpwdWJsaWM6CglpbnQgbWluUHVzaEJveCh2ZWN0b3I8dmVjdG9yPGNoYXI+PiYgZ3JpZCkKCXsKCQlhPWdyaWQ7CgkJZHAuY2xlYXIoKTsKCQluPWEuc2l6ZSgpLG09YVswXS5zaXplKCk7CgkJZm9yKGludCBpPTA7aTxuO2krKykKCQkJZm9yKGludCBqPTA7ajxtO2orKykKCQkJCWlmKGFbaV1bal09PSdCJykgYng9aSxieT1qOwoJCQkJZWxzZSBpZihhW2ldW2pdPT0nUycpIHN4PWksc3k9ajsKCQkJCWVsc2UgaWYoYVtpXVtqXT09J1QnKSB0eD1pLHR5PWo7CgoJCXF1ZXVlIDxwYWlyIDxwYWlyIDxpbnQsaW50PixwYWlyIDxpbnQsaW50Pj4+IGN1cjsKCQlhZGQoYngsYnksc3gsc3ksY3VyLDApOwoJCXdoaWxlKG5vdCBjdXIuZW1wdHkoKSkKCQl7CgkJCXF1ZXVlIDxwYWlyIDxwYWlyIDxpbnQsaW50PixwYWlyIDxpbnQsaW50Pj4+IG54dDsKCQkJd2hpbGUobm90IGN1ci5lbXB0eSgpKQoJCQl7CgkJCQlhdXRvIHBwPWN1ci5mcm9udCgpOwoJCQkJY3VyLnBvcCgpOwoKCQkJCWludCBkaXN0PWRwW3BwXTsKCQkJCWF1dG8gYm94PXBwLmZpcnN0OwoJCQkJYXV0byBzaG9wa2VlcGVyPXBwLnNlY29uZDsKCQkJCWlmKGJveC5maXJzdD09dHggYW5kIGJveC5zZWNvbmQ9PXR5KSByZXR1cm4gZGlzdDsKCgkJCQlmb3IoaW50IGs9MDtrPDQ7aysrKQoJCQkJewoJCQkJCWludCBuc3g9c2hvcGtlZXBlci5maXJzdCtkeFtrXSxuc3k9c2hvcGtlZXBlci5zZWNvbmQrZHlba107CgkJCQkJaWYoaW52YWxpZChuc3gsbnN5KSkgY29udGludWU7CgkJCQkJaWYobnN4PT1ib3guZmlyc3QgYW5kIG5zeT09Ym94LnNlY29uZCkKCQkJCQl7CgkJCQkJCWlmKGludmFsaWQoYm94LmZpcnN0K2R4W2tdLGJveC5zZWNvbmQrZHlba10pKSBjb250aW51ZTsKCQkJCQkJYWRkKGJveC5maXJzdCtkeFtrXSxib3guc2Vjb25kK2R5W2tdLG5zeCxuc3ksbnh0LGRpc3QrMSk7CgkJCQkJfQoJCQkJCWVsc2UgYWRkKGJveC5maXJzdCxib3guc2Vjb25kLG5zeCxuc3ksY3VyLGRpc3QpOwoJCQkJfQoJCQl9CgkJCWN1cj1ueHQ7CgkJfQoKCQlyZXR1cm4gLTE7Cgl9Cn07CgojaWZkZWYgTE9DQUwKaW50IG1haW4oKQp7Cgl2ZWN0b3IgPGludD4gdj17MSwyfTsKCWF1dG8gYW5zPVNvbHV0aW9uKCkubWF4U3VtRGl2VGhyZWUodik7Cn0KI2VuZGlm