結果

問題 No.340 雪の足跡
ユーザー kapokapo
提出日時 2016-05-19 13:36:36
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,841 bytes
コンパイル時間 813 ms
コンパイル使用メモリ 79,388 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-10-06 06:08:11
合計ジャッジ時間 13,534 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
11,008 KB
testcase_01 AC 7 ms
11,008 KB
testcase_02 AC 8 ms
11,008 KB
testcase_03 AC 7 ms
11,008 KB
testcase_04 AC 8 ms
11,008 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 7 ms
11,008 KB
testcase_07 AC 7 ms
11,008 KB
testcase_08 AC 8 ms
11,008 KB
testcase_09 AC 7 ms
11,008 KB
testcase_10 AC 7 ms
11,008 KB
testcase_11 AC 8 ms
11,008 KB
testcase_12 AC 7 ms
11,264 KB
testcase_13 AC 8 ms
11,136 KB
testcase_14 AC 20 ms
11,264 KB
testcase_15 AC 24 ms
11,392 KB
testcase_16 AC 18 ms
11,264 KB
testcase_17 AC 30 ms
11,520 KB
testcase_18 AC 25 ms
11,520 KB
testcase_19 AC 30 ms
11,392 KB
testcase_20 TLE -
testcase_21 AC 862 ms
14,976 KB
testcase_22 AC 7 ms
11,008 KB
testcase_23 AC 514 ms
14,976 KB
testcase_24 TLE -
testcase_25 AC 757 ms
14,976 KB
testcase_26 AC 39 ms
11,776 KB
testcase_27 AC 12 ms
11,136 KB
testcase_28 AC 36 ms
11,520 KB
testcase_29 AC 491 ms
14,592 KB
testcase_30 AC 265 ms
13,568 KB
testcase_31 AC 524 ms
14,336 KB
testcase_32 AC 644 ms
14,976 KB
testcase_33 AC 489 ms
14,208 KB
testcase_34 AC 658 ms
14,976 KB
testcase_35 TLE -
testcase_36 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <vector>
#include <map>

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
using namespace std;

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int w, h, n, t1, t2, x1, y1, x2, y2, x, y, i, j;
	cin >> w >> h >> n;
	if(h == 1 && w == 1) { cout << 0 << endl; return 0; }
	vector<int> v;
	vector<vector<int> > lt;
	rep(i, 0, n) {
		v.clear();
		cin >> t1;
		rep(j, 0, t1+1) { cin >> t2; v.pb(t2); }
		lt.pb(v);
	}

	int bf[4] = {1,2,4,8}; // N E W S
	vector<vector<int> > dp(1000, vector<int>(1000, 0));
	vector<vector<int> > mp(1000, vector<int>(1000, 0));

	for(auto vec : lt) {
		rep(j, 0, (int)vec.size()-1) {
			y1 = vec[j]/w; x1 = vec[j]%w;
			y2 = vec[j+1]/w; x2 = vec[j+1]%w;
			if(y1 == y2) {
				if(x1 < x2) {
					rep(i,0,x2-x1) {
						mp[y1][x1+i] |= bf[1];
						mp[y1][x1+1+i] |= bf[2];
					}
				}
				else if(x1 > x2) {
					rep(i,0,x1-x2) {
						mp[y1][x1-i] |= bf[2];
						mp[y1][x1-1-i] |= bf[1];
					}
				}
			}
			else if(x1 == x2) {
				if(y1 < y2) {
					rep(i,0,y2-y1) {
						mp[y1+i][x1] |= bf[0];
						mp[y1+1+i][x1] |= bf[3];
					}
				}
				else if(y1 > y2) {
					rep(i,0,y1-y2) {
						mp[y1-i][x1] |= bf[3];
						mp[y1-1-i][x1] |= bf[0];
					}
				}
			}
		}
	}

	pair<int, int> p;
	queue<pair<int, int> > q;
	q.push(pair<int, int>(0,0));
	int ym[4] = {1, 0, 0, -1};
	int xm[4] = {0, 1, -1, 0};

	while(q.size()) {
		p = q.front();
		y = p.first; x = p.second;
		q.pop();

		rep(i,0,4) {
			if(!(mp[y][x] & bf[i])) continue;
			if(dp[y + ym[i]][x + xm[i]] == 0 || dp[ y+ym[i] ][ x+xm[i] ] > dp[y][x]+1) {
				dp[y + ym[i]][x + xm[i]] = dp[y][x] + 1;
				p.first = y+ym[i]; p.second = x+xm[i];
				q.push(p);
			}
		}
	}

	dp[h-1][w-1]? cout << dp[h-1][w-1] << endl : cout << "Odekakedekinai.." << endl;

	return 0;
}
0