結果

問題 No.340 雪の足跡
コンテスト
ユーザー tancahn2380
提出日時 2018-04-01 15:59:45
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,147 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 960 ms
コンパイル使用メモリ 109,804 KB
実行使用メモリ 17,280 KB
最終ジャッジ日時 2024-06-26 05:27:49
合計ジャッジ時間 8,476 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 28 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
# define ALL(x)      (x).begin(),(x).end()
# define UNIQ(c)     (c).erase(unique(ALL((c))),(c).end())
# define LOWER(s)    transform(ALL((s)),(s).begin(),TL<char>)
# define UPPER(s)    transform(ALL((s)),(s).begin(),TU<char>)
# define mp          make_pair
# define eb          emplace_back
# define FOR(i,a,b)  for(LL i=(a);i<(b);i++)
# define RFOR(i,a,b) for(LL i=(a);i>=(b);i--)
# define REP(i,n)    FOR(i,0,n)
# define INIT        std::ios::sync_with_stdio(false);std::cin.tie(0)

int w, h, n;
int m, b[1010];
int cnt[1010][1010], cnt2[1010][1010];
bool isok1[1010][1010], isok2[1010][1010];

int sx, sy, gx, gy;

int d[1001][1001];
int bfs() {
	queue<pair<int, int>> que;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			d[i][j] = HINF;
		}
	}
	que.push(pair<int, int>(sx, sy));
	d[sy][sx] = 0;
	while (que.size()) {
		pair<int, int> p = que.front();
		que.pop();
		for (int i = 0; i < 4; i++) {
			int nx = p.first + dx[i], ny = p.second + dy[i];
			if (nx != p.first) {
				if (!isok1[ny][max(p.first, nx)])continue;
			}
			if (ny != p.second) {
				if (!isok2[max(p.second, ny)][nx])continue;
			}
			if (0 <= nx&&nx < w && 0 <= ny&&ny < h &&d[ny][nx] == HINF) {
				que.push(pair<int, int>(nx, ny));
				d[ny][nx] = d[p.second][p.first] + 1;
			}
		}
	}
	return d[gy][gx];
}


int main() {
	cin >> w >> h >> n;
	REP(po, n) {
		cin >> m;
		REP(k, m + 1) {
			cin >> b[k];
			if (k) {
				int ki = b[k] / w;
				int kj = b[k] % w;
				int prei = b[k - 1] / w;
				int prej = b[k - 1] % w;
				if (prei == ki) {
					int mij = min(kj, prej);
					int maj = max(kj, prej);
					cnt[ki][mij]++;
					cnt[kj][maj + 1]--;
				}
				else {
					int mii = min(ki, prei);
					int mai = max(ki, prei);
					cnt2[mii][kj]++;
					cnt2[mai + 1][kj]--;
				}
			}
		}
	}
	REP(i, h)REP(j, w) {
		if (j) {
			cnt[i][j] += cnt[i][j - 1];
			if (cnt[i][j] > 0 && cnt[i][j - 1] > 0)isok1[i][j] = true;
		}
	}
	REP(i, h)REP(j, w) {
		if (i) {
			cnt2[i][j] += cnt2[i - 1][j];
			if (cnt2[i][j] > 0 && cnt2[i - 1][j] > 0)isok2[i][j] = true;
		}
	}
	gy = h - 1, gx = w - 1;
	LL ret = bfs();
	if (ret == HINF) {
		cout << "Odekakedekinai.." << endl;
	}
	else {
		cout << ret << endl;
	}
	//system("pause");
}
0