Skip to content

Instantly share code, notes, and snippets.

@mi6112ogit
Created September 18, 2017 16:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mi6112ogit/a68c9a4a9079e3fcb551c5396b4abff7 to your computer and use it in GitHub Desktop.
Save mi6112ogit/a68c9a4a9079e3fcb551c5396b4abff7 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF (1 << 30)
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
int H, W, N;
string field[1001];
int went[1001][1001];
int sx, sy;
int bfs(int y, int x, char lv) {
memset(went, 0, sizeof(went));
queue<Pi> que;
que.push(Pi(P(y, x), 0));
while(!que.empty()) {
Pi p = que.front(); que.pop();
if(went[p.first.first][p.first.second]) continue;
if(field[p.first.first][p.first.second] == lv) {
sy = p.first.first; sx = p.first.second;
return p.second;
}
went[p.first.first][p.first.second] = 1;
rep(i, 4) {
int ny = p.first.first + dy[i];
int nx = p.first.second + dx[i];
if(0 <= ny && ny < H && 0 <= nx && nx < W && field[ny][nx] != 'X') {
que.push(Pi(P(ny, nx), p.second + 1));
}
}
}
return 0;
}
signed main() {
scanf("%d %d %d", &H, &W, &N);
rep(i, H) cin >> field[i];
rep(i, H) rep(j, W) {
if(field[i][j] == 'S') {
sy = i; sx = j;
}
}
int res = 0;
char lv = '1';
rep(i, N) {
res += bfs(sy, sx, lv + i);
}
printf("%d\n", res);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment