This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll mod=1e9+7;
const ll maxn=1010;
const ll inf=1e9+900;
const ll maxm=maxn*maxn;
const ll di[4]={+1,-1,0,0};
const ll dj[4]={0,0,+1,-1};
vector<pii> ger[maxm];
ll dp[maxm];
ll fas(ll a,ll b){
set<pii> st;
st.insert(mp(0,a));
fill(dp,dp+maxm,inf);
while(st.size()){
pii e=(*st.begin());
st.erase(e);
ll v=e.S;
ll w=e.F;
if(dp[v]>w){
dp[v]=w;
for(auto t:ger[v]){
if(dp[t.F]==inf){
st.insert(mp(t.S+w,t.F));
}
}
}
}
if(dp[b]==inf)dp[b]=-1;
return dp[b];
}
string s[maxn];
ll minn[maxm];
ll ta[maxm][4];
ll n,m;
ll getid(ll a,ll b){
return a*maxn+b;
}
bool val(ll a,ll b){
return (!(a<0 || b<0 || a>=n || b>=m || s[a][b]=='#'));
}
void addYal(ll a,ll b,ll c){
if(a==b)return;
ger[a].pb(mp(b,c));
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(ll i=0;i<n;i++){
cin>>s[i];
}
fill(minn,minn+maxm,inf);
queue<ll> qu;
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
ll id=getid(i,j);
if(s[i][j]!='#'){
for(ll y=0;y<4;y++){
if(val(i+di[y],j+dj[y])){
addYal(getid(i,j),getid(i+di[y],j+dj[y]),1);
}else if(minn[id]==inf){
minn[id]=1;
qu.push(id);
}
}
}
}
}
while(qu.size()){
ll v=qu.front();
qu.pop();
for(auto e:ger[v]){
ll u=e.F;
if(minn[u]==inf){
minn[u]=minn[v]+1;
qu.push(u);
}
}
}
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
ll id=getid(i,j);
if(val(i+di[1],j+dj[1])){
ta[id][1]=ta[getid(i+di[1],j+dj[1])][1];
}else{
ta[id][1]=id;
}
if(val(i+di[3],j+dj[3])){
ta[id][3]=ta[getid(i+di[3],j+dj[3])][3];
}else{
ta[id][3]=id;
}
}
}
for(ll i=n-1;i>=0;i--){
for(ll j=m-1;j>=0;j--){
ll id=getid(i,j);
if(val(i+di[2],j+dj[2])){
ta[id][2]=ta[getid(i+di[2],j+dj[2])][2];
}else{
ta[id][2]=id;
}
if(val(i+di[0],j+dj[0])){
ta[id][0]=ta[getid(i+di[0],j+dj[0])][0];
}else{
ta[id][0]=id;
}
}
}
ll start;
ll end;
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
if(s[i][j]!='#'){
ll id=getid(i,j);
if(s[i][j]=='S')start=id;
if(s[i][j]=='C')end=id;
for(ll y=0;y<4;y++){
addYal(id,ta[id][y],minn[id]);
}
}
}
}
cout<<fas(start,end);
}
Compilation message (stderr)
portals.cpp: In function 'int main()':
portals.cpp:144:24: warning: 'end' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout<<fas(start,end);
^
portals.cpp:144:24: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |