結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
11,136 KB
testcase_01 AC 8 ms
11,136 KB
testcase_02 AC 8 ms
11,136 KB
testcase_03 AC 7 ms
11,008 KB
testcase_04 AC 7 ms
11,008 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 8 ms
11,008 KB
testcase_07 AC 7 ms
11,008 KB
testcase_08 AC 8 ms
11,008 KB
testcase_09 AC 8 ms
11,008 KB
testcase_10 AC 8 ms
11,008 KB
testcase_11 AC 8 ms
11,136 KB
testcase_12 AC 8 ms
11,264 KB
testcase_13 AC 8 ms
11,008 KB
testcase_14 AC 21 ms
11,264 KB
testcase_15 AC 24 ms
11,648 KB
testcase_16 AC 19 ms
11,264 KB
testcase_17 AC 30 ms
11,520 KB
testcase_18 AC 25 ms
11,520 KB
testcase_19 AC 31 ms
11,392 KB
testcase_20 TLE -
testcase_21 AC 880 ms
14,976 KB
testcase_22 AC 7 ms
11,136 KB
testcase_23 AC 525 ms
14,976 KB
testcase_24 TLE -
testcase_25 AC 767 ms
14,976 KB
testcase_26 AC 41 ms
11,776 KB
testcase_27 AC 12 ms
11,264 KB
testcase_28 AC 37 ms
11,648 KB
testcase_29 AC 498 ms
14,592 KB
testcase_30 AC 271 ms
13,440 KB
testcase_31 AC 533 ms
14,336 KB
testcase_32 AC 660 ms
14,848 KB
testcase_33 AC 502 ms
14,208 KB
testcase_34 AC 673 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