結果
問題 | No.340 雪の足跡 |
ユーザー |
![]() |
提出日時 | 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); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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(); }