Submission #71670007

---

Source Code Expand

#include <bits/stdc++.h>
//#include <windows.h>
//taskkill /f /im 未命名1.exe
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define pr(a,l,r) for(int i=l;i<=r;++i) cerr<<a[i]<<' ';ED
#define popcnt __builtin_popcount
#define all(s) s.begin(),s.end()
#define bstring basic_string
//#define add(x,y) (x+=y)%=mod
#define pii pair<int,int>
#define epb emplace_back
#define pb push_back
#define mk make_pair
#define ins insert
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=1e3+5,INF=0x3f3f3f3f,mod=1e9+7;
int t,n,m,ans=0;
char s[N][N];vector<pii> S[30];
int dr[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int dis[N][N],vis[N][N];

bool in(int x,int y) {
	return x>=1&&x<=n&&y>=1&&y<=m;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j) {
			if(s[i][j]!='.'&&s[i][j]!='#') {
				S[s[i][j]-'a'].epb(i,j);
			}
		}
	}
	deque<pii> q;
	memset(dis,0x3f,sizeof(dis));
	dis[1][1]=0,q.push_front({1,1});
	while(!q.empty()) {
		pii u=q.front();q.pop_front();
		if(vis[u.fi][u.se]) continue;
		vis[u.fi][u.se]=1;
		if(u.se) {
			for(int j=0;j<4;++j) {
				int tx=u.fi+dr[j][0];
				int ty=u.se+dr[j][1];
				if(in(tx,ty)&&s[tx][ty]!='#'&&dis[u.fi][u.se]+1<dis[tx][ty]) {
					dis[tx][ty]=dis[u.fi][u.se]+1;
					q.push_back({tx,ty});
				}
			}
			int op=s[u.fi][u.se]-'a';
			if(op>=0&&op<26) {
				if(dis[u.fi][u.se]<dis[op][0]) {
					dis[op][0]=dis[u.fi][u.se];
					q.push_front({op,0});
				}
			}
		}
		else {
			for(auto it:S[u.fi]) {
				if(dis[u.fi][u.se]+1<dis[it.fi][it.se]) {
					dis[it.fi][it.se]=dis[u.fi][u.se]+1;
					q.push_back(it);
				}
			}
		}
	}
	if(dis[n][m]>INF/2) puts("-1"); 
	else printf("%d\n",dis[n][m]);
	return 0;
}

Submission Info

Judge Result