Submission #1735778

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define RREP(i,a,b) for(int i=(a);i>=(b);i--)
#define pq priotity_queue
typedef long long ll; typedef long double ld;
using namespace std;
const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};
const ld PI=abs(acos(-1));
int h,w,k,min_cost[1010][1010];
string li[1010];

int bfs(int sx, int sy, char c){
	const int vx[]={0,1,0,-1}, vy[]={1,0,-1,0};
	memset(min_cost, -1, sizeof(min_cost));
	
	queue<pair<int,int>> que;
	que.emplace(sx,sy);
	min_cost[sx][sy]=0;
	
	while(!que.empty()){
		auto p=que.front(); que.pop();
		
		if(li[p.first][p.second]==c) return min_cost[p.first][p.second];
		REP(i,0,4){
			int nx=p.first+vx[i], ny=p.second+vy[i];
			if(nx<0 or ny<0 or nx>=h or ny>=w) continue;
			if(min_cost[nx][ny]!=-1) continue;
			if(li[nx][ny]=='X') continue;
			min_cost[nx][ny]=min_cost[p.first][p.second]+1;
			que.emplace(nx,ny);
		}
	}
	
	return -1;
}
	
int main(){
	cin >> h >> w >> k;
	REP(i,0,h) cin >> li[i];
	
	vector<pair<int,pair<int,int>>> vec;
	REP(i,0,h) REP(j,0,w) if(li[i][j]=='S') vec.push_back(make_pair(0,make_pair(i,j)));
	REP(i,0,h) REP(j,0,w) REP(l,1,k+1) if(li[i][j]==l+'0') vec.push_back(make_pair(l,make_pair(i,j)));
	sort(vec.begin(),vec.end());
	
	ll s=0;
	REP(j,0,vec.size()-1) s+=bfs(vec[j].second.first,vec[j].second.second,vec[j].first+'1');	
	
	cout << s << endl;
	return 0;
}

Submission Info

Judge Result