Submission #74034626

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#define INF 1010101010
int H, W;
char S[1024][1024];
struct edge_s {
  int to, cost;
};
int ec[1024 * 1024 + 100];
struct edge_s* es[1024 * 1024 + 100];
void ae(int f, int t, int c) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = (struct edge_s){ t, c };
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

#define INF 1010101010

int H, W;
char S[1024][1024];

struct edge_s {
	int to, cost;
};

int ec[1024 * 1024 + 100];
struct edge_s* es[1024 * 1024 + 100];

void ae(int f, int t, int c) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = (struct edge_s){ t, c };
}

void try_ae(int fy, int fx, int ty, int tx) {
	if (fy < 0 || H <= fy || fx < 0 || W <= fx) return;
	if (ty < 0 || H <= ty || tx < 0 || W <= tx) return;
	if (S[fy][fx] == '#' || S[ty][tx] == '#') return;
	ae(fy * W + fx, ty * W + tx, 1);
}

int mincost[1024 * 1024 + 100];

int q[(1024 * 1024 * 6 + 30 * 1024 * 1024) * 2];

int main(void) {
	int i, j;
	int qs = 1024 * 1024 * 6 + 30 * 1024 * 1024;
	int qe = qs;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 0; i < H; i++) {
		if (scanf("%1023s", S[i]) != 1) return 1;
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			try_ae(i, j, i - 1, j);
			try_ae(i, j, i + 1, j);
			try_ae(i, j, i, j - 1);
			try_ae(i, j, i, j + 1);
			if ('a' <= S[i][j] && S[i][j] < 'a' + 26) {
				int id = S[i][j] - 'a';
				int cur = i * W + j;
				int meta = H * W + id;
				ae(cur, meta, 1);
				ae(meta, cur, 0);
			}
		}
	}
	/* コストが0か1しかないとき、0ならunshiftすることでダイクストラ法を回避するやつ */
	for (i = 0; i < H * W + 26; i++) mincost[i] = INF;
	mincost[0] = 0;
	q[qe++] = 0;
	while (qs < qe) {
		int cur = q[qs++];
		for (i = 0; i < ec[cur]; i++) {
			if (mincost[cur] + es[cur][i].cost < mincost[es[cur][i].to]) {
				mincost[es[cur][i].to] = mincost[cur] + es[cur][i].cost;
				if (es[cur][i].cost == 0) {
					q[--qs] = es[cur][i].to;
				} else {
					q[qe++] = es[cur][i].to;
				}
			}
		}
	}
	printf("%d\n", mincost[H * W - 1] < INF ? mincost[H * W - 1] : -1);
	return 0;
}

Submission Info

Judge Result