結果

問題 No.340 雪の足跡
ユーザー 🍡yurahuna🍡yurahuna
提出日時 2016-02-27 10:48:31
言語 C++11
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 2,693 bytes
コンパイル時間 1,290 ms
コンパイル使用メモリ 80,648 KB
実行使用メモリ 554,424 KB
最終ジャッジ日時 2024-09-24 11:23:14
合計ジャッジ時間 4,682 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 1 MLE * 1 -- * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void mark()’:
main.cpp:43:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |         scanf("%d", &M);
      |         ~~~~~^~~~~~~~~~
main.cpp:50:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |                 scanf("%d", &B[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp: In function ‘void input()’:
main.cpp:71:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |         scanf("%d%d%d", &W, &H, &N);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <complex>
#include <queue>
#include <map>
#include <string>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)

#define PI 3.1415926535

typedef long long ll;
typedef pair<int, int> P;
//typedef complex<double> C;

const int INF = 99999999;
const int MAX_W = 1000;
const int MAX_H = 1000;
const int MAX_N = 1000;
const int MAX_M = 1000;

int W, H, N;
int B[MAX_M + 1];
int imos1[MAX_H + 1][MAX_W + 1];	// row
int imos2[MAX_H + 1][MAX_W + 1];	// col
int d[MAX_H][MAX_W];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void mark() {
	int M;
	scanf("%d", &M);
	// vector<int> B(M);
	// REP(i, M + 1) {
	// 	scanf("%d", &B[i]);
	// }
	REP(i, MAX_M + 1) B[i] = 0;
	REP(i, M + 1) {
		scanf("%d", &B[i]);
	}
	REP(i, M) {
		int r1, c1, r2, c2;
		r1 = B[i] / H;
		r2 = B[i + 1] / H;
		c1 = B[i] % W;
		c2 = B[i + 1] % W;
		if(r1 == r2) {
			// 横に歩いた
			imos1[r1][min(c1, c2)] = 1;
			imos1[r1][max(c1, c2) + 1] = -1;
		} else {
			// 縦に歩いた
			imos2[min(r1, r2)][c1] = 1;
			imos2[max(r1, r2) + 1][c1] = -1;
		}
	}
}

void input() {
	scanf("%d%d%d", &W, &H, &N);
	REP(i, N) {
		mark();
	}
}

void makeField() {
	REP(i, H) {
		REP(j, W) {
			imos1[i][j + 1] += imos1[i][j];
			imos2[i + 1][j] += imos2[i][j];
		}
	}
}

bool inside(int x, int y) {
    return x >= 0 && x < H && y >= 0 && y < W;
}

bool canMove(int r1, int c1, int r2, int c2) {
	if (r1 == r2) {
		// 横に移動したい
		// 今いるマスと次に行くマスがどちらも0でないなら移動できる
		return imos1[r1][c1] * imos1[r2][c2] > 0;
	} else {
		return imos2[r1][c1] * imos2[r2][c2] > 0;
	}
}

int bfs(int sx, int sy, int gx, int gy) {
	REP(i, H) REP(j, W) d[i][j] = INF;
    d[sx][sy] = 0;

    queue<P> que;
    que.push(P(sx, sy));

    while (!que.empty()) {
        P p = que.front(); que.pop();
		int x = p.first, y = p.second;
        if (x == gx && y == gy)
            break;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];

            if (inside(nx, ny) && canMove(x, y, nx, ny)) {
                que.push(P(nx, ny));
                d[nx][ny] = d[x][y] + 1;
            }
        }
    }
    return d[gx][gy];
}

void solve() {
	makeField();
	int ans = bfs(0, 0, H - 1, W - 1);
	if (ans < INF) {
		printf("%d\n", ans);
	} else {
		printf("Odekakedekinai..\n");
	}
}

int main() {
	input();
	solve();
}
0