結果
| 問題 | No.1323 うしらずSwap |
| ユーザー |
 kotatsugame
|
| 提出日時 | 2020-12-20 23:39:56 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 967 ms / 3,000 ms |
| コード長 | 3,798 bytes |
| コンパイル時間 | 1,222 ms |
| コンパイル使用メモリ | 92,632 KB |
| 実行使用メモリ | 151,296 KB |
| 最終ジャッジ日時 | 2024-11-15 09:41:24 |
| 合計ジャッジ時間 | 13,281 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 59 |
コンパイルメッセージ
a.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
ソースコード
#line 1 "a.cpp"#include<iostream>#include<queue>using namespace std;#line 1 "/home/kotatsugame/library/graph/MCF.cpp"//Minimum Cost Flow O(FE log V)#include<algorithm>#include<utility>#include<vector>#line 6 "/home/kotatsugame/library/graph/MCF.cpp"#include<limits>template<typename T>struct MCF{struct edge{int to,rev,cap;T cost;};vector<vector<edge> >G;vector<T>h,d;vector<int>pv,pe;MCF(int n_=0):G(n_),h(n_,0),d(n_),pv(n_),pe(n_){}void add_edge(int from,int to,int cap,T cost){G[from].push_back({to,(int)G[to].size(),cap,cost});G[to].push_back({from,(int)G[from].size()-1,0,-cost});}T min_cost_flow(int s,int t,int f)//ans or -1{T ret=0;while(f>0){priority_queue<pair<T,int>,vector<pair<T,int> >,greater<pair<T,int> > >P;fill(d.begin(),d.end(),numeric_limits<T>::max());d[s]=0;P.push(make_pair(0,s));while(!P.empty()){pair<T,int>p=P.top();P.pop();if(d[p.second]<p.first)continue;for(int i=0;i<G[p.second].size();i++){edge&e=G[p.second][i];if(e.cap>0&&d[e.to]>d[p.second]+e.cost+h[p.second]-h[e.to]){d[e.to]=d[p.second]+e.cost+h[p.second]-h[e.to];pv[e.to]=p.second;pe[e.to]=i;P.push(make_pair(d[e.to],e.to));}}}if(d[t]==numeric_limits<T>::max())return -1;for(int u=0;u<G.size();u++)h[u]+=d[u];int d=f;for(int u=t;u!=s;u=pv[u])d=min(d,G[pv[u]][pe[u]].cap);f-=d;ret+=d*h[t];for(int u=t;u!=s;u=pv[u]){G[pv[u]][pe[u]].cap-=d;G[u][G[pv[u]][pe[u]].rev].cap+=d;}}return ret;}};#line 5 "a.cpp"int H,W,sx,sy,gx,gy;string s[1333];int dist[1333][1333];int d[5]={0,1,0,-1};main(){cin>>H>>W>>sx>>sy>>gx>>gy;for(int i=0;i<H;i++)cin>>s[i];for(int i=0;i<H;i++)for(int j=0;j<W;j++)dist[i][j]=1e9;sx--,sy--;gx--,gy--;dist[sx][sy]=0;queue<pair<int,int> >P;P.push(make_pair(sx,sy));while(!P.empty()){int x=P.front().first,y=P.front().second;P.pop();for(int r=0;r<4;r++){int tx=x+d[r],ty=y+d[r+1];if(s[tx][ty]=='#'||dist[tx][ty]<=dist[x][y]+1)continue;dist[tx][ty]=dist[x][y]+1;P.push(make_pair(tx,ty));}}if(dist[gx][gy]==(int)1e9){cout<<-1<<endl;return 0;}bool fn=false,two=false;int x=gx,y=gy;while(x!=sx||y!=sy){int nx=-1,ny=-1;int cnt=0;for(int r=0;r<4;r++){int tx=x+d[r],ty=y+d[r+1];if(s[tx][ty]=='#')continue;if(dist[tx][ty]==dist[x][y]-1){if(nx<0)nx=tx,ny=ty;else two=true;}cnt++;}if((x!=gx||y!=gy)&&cnt>=3)fn=true;x=nx;y=ny;}if(two){cout<<dist[gx][gy]*2<<endl;return 0;}else if(fn){cout<<dist[gx][gy]*2+2<<endl;return 0;}MCF<int>F(H*W);for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(s[i][j]=='.'){for(int r=0;r<4;r++){int tx=i+d[r],ty=j+d[r+1];if(s[tx][ty]=='.')F.add_edge(i*W+j,tx*W+ty,1,1);}}int ans=F.min_cost_flow(sx*W+sy,gx*W+gy,2);if(ans==-1)ans=1e9;for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(dist[i][j]<(int)1e9){int cnt=0;for(int r=0;r<4;r++){int x=i+d[r],y=j+d[r+1];if(s[x][y]=='.')cnt++;}if(cnt>=3)ans=min(ans,dist[gx][gy]*2+4+dist[i][j]*4);}for(int i=0;i<H;i++)for(int j=0;j<W;j++)dist[i][j]=1e9;dist[gx][gy]=0;P.push(make_pair(gx,gy));while(!P.empty()){int x=P.front().first,y=P.front().second;P.pop();for(int r=0;r<4;r++){int tx=x+d[r],ty=y+d[r+1];if(s[tx][ty]=='#'||dist[tx][ty]<=dist[x][y]+1)continue;dist[tx][ty]=dist[x][y]+1;P.push(make_pair(tx,ty));}}for(int i=0;i<H;i++)for(int j=0;j<W;j++)if(dist[i][j]<(int)1e9){int cnt=0;for(int r=0;r<4;r++){int x=i+d[r],y=j+d[r+1];if(s[x][y]=='.')cnt++;}if(cnt>=3)ans=min(ans,dist[sx][sy]*2+4+dist[i][j]*4);}cout<<(ans<(int)1e9?ans:-1)<<endl;}