結果
問題 | No.1323 うしらずSwap |
ユーザー |
|
提出日時 | 2020-12-20 01:13:06 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 233 ms / 3,000 ms |
コード長 | 2,935 bytes |
コンパイル時間 | 1,743 ms |
コンパイル使用メモリ | 174,744 KB |
実行使用メモリ | 55,044 KB |
最終ジャッジ日時 | 2024-11-15 09:32:25 |
合計ジャッジ時間 | 10,161 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 59 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define F first#define S second#define R cin>>#define ll long long#define ln cout<<'\n'#define in(a) insert(a)#define pb(a) push_back(a)#define pd(a) printf("%.10f\n",a)#define mem(a) memset(a,0,sizeof(a))#define all(c) (c).begin(),(c).end()#define iter(c) __typeof((c).begin())#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)#define rep(i,n) REP(i,0,n)#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};typedef pair<ll,ll> P;ll n,m;string s[2222];vector<vector<ll> > bfs(int sx,int sy) {vector<vector<ll> > d(n,vector<ll>(m,MAX));d[sx][sy]=0;queue<P> que;que.push(P(sx,sy));while(!que.empty()) {P p=que.front();que.pop();ll x=p.F,y=p.S;rep(i,4) {ll xx=x+dx[i],yy=y+dy[i];if(check(n,m,xx,yy)&&s[xx][yy]=='.'&&d[xx][yy]==MAX) {d[xx][yy]=d[x][y]+1;que.push(P(xx,yy));}}}return d;}void Main() {ll sx,sy,tx,ty;cin >> n >> m >> sx >> sy >> tx >> ty;rep(i,n) cin >> s[i];sx--,sy--,tx--,ty--;vector<vector<ll> > c=bfs(sx,sy);vector<vector<ll> > d=bfs(tx,ty);ll ans=MAX;vector<P> v;rep(i,n) {rep(j,m) {if(s[i][j]=='.') {ll dd=c[i][j]+d[i][j];if(dd==c[tx][ty]) v.pb(P(i,j));}}}if(v.size()>c[tx][ty]+1) {pr(c[tx][ty]*2);return;}rep(i,n) {rep(j,m) {if(s[i][j]=='#') continue;ll dd=c[i][j]+d[i][j];if(dd==c[tx][ty]) {vector<P> v;rep(k,4) {int x=i+dx[k],y=j+dy[k];if(check(n,m,x,y)&&s[x][y]=='.') {ll cc=c[x][y]+d[x][y];if(cc!=dd) v.pb(P(x,y));}}if(P(i,j)!=P(sx,sy)&&P(i,j)!=P(tx,ty)) {if(v.size()) ans=min(ans,dd*2+2);} else {if(v.size()>=2) ans=min(ans,dd*2+4);}}if(c[i][j]==d[sx][sy]+d[i][j]||d[i][j]==c[tx][ty]+c[i][j]) {vector<P> v;rep(k,4) {int x=i+dx[k],y=j+dy[k];if(check(n,m,x,y)&&s[x][y]=='.') {ll cc=c[x][y]+d[x][y];v.pb(P(x,y));}}if(v.size()>=3) ans=min(ans,(c[i][j]+d[i][j])*2+4);}}}s[sx][sy]='#';rep(k,4) {ll x=sx+dx[k],y=sy+dy[k];if(check(n,m,x,y)&&s[x][y]=='.'&&d[x][y]+c[x][y]!=c[tx][ty]) {vector<vector<ll> > e=bfs(x,y);ll dd=d[sx][sy]+e[tx][ty]+1;ans=min(ans,dd);}}if(ans==MAX) ans=-1;pr(ans);}int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}