結果

問題 No.340 雪の足跡
ユーザー 🍡yurahuna🍡yurahuna
提出日時 2016-02-27 10:42:38
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,592 bytes
コンパイル時間 959 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 7,892 KB
最終ジャッジ日時 2023-10-24 18:24:48
合計ジャッジ時間 7,166 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,888 KB
testcase_01 AC 2 ms
7,892 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
7,888 KB
testcase_04 AC 2 ms
7,888 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void mark()’:
main.cpp:42:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |         scanf("%d", &M);
      |         ~~~~~^~~~~~~~~~
main.cpp:45:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |                 scanf("%d", &B[i]);
      |                 ~~~~~^~~~~~~~~~~~~
main.cpp: In function ‘void input()’:
main.cpp:66:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |         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 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, 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