第10回日本情報オリンピック 予選(オンライン)

Submission #1359274

Source codeソースコード

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define OREP(i,n) FOR(i,1,n)
#define GREY 2
#define WHITE 1
#define BLACK 0
#define x first
#define y second
typedef pair<queue<ll>, queue<ll>> a;

ll h, w, n, dp[1000][1000] = { -1 }, houkou[] = { 0, 1, 0, -1, 0 }, saishox, saishoy;
char retu[1000][1000];

bool in(ll xx, ll yy) {
	if (xx >= 0 && yy >= 0 && xx < h&& yy < w) {
		return true;
	}
	return false;
}

int main() {
	a que; queue<ll>hp;
	cin >> h >> w >> n;
	REP(i, h) {
		REP(j, w) {
			cin >> retu[i][j];
			if (retu[i][j] == 'S') {
				saishox = i; saishoy = j; retu[i][j] = '.';
			}
		}
	}
	que.x.push(saishox); que.y.push(saishoy); hp.push(1);
	queue<ll>minuites, nokori; minuites.push(0); nokori.push(n);
	ll count = 0, min = 0, beforex = -1, beforey = -1;

	while (!que.x.empty()) {
		ll nx = que.x.front(), ny = que.y.front(), nannko = nokori.front(), h = hp.front(); nokori.pop(); hp.pop(); min = minuites.front(); minuites.pop();
		if(nannko==0){ cout << min  << endl; break; }
		que.x.pop(); que.y.pop();
		//一度他のパターンで行ってしまったチーズ工場のところにたどり着いてもなにもおこらないバグ
		REP(i, 4) {
			ll xx = houkou[i] + nx, yy = houkou[i + 1] + ny;//xとyの位置をメモ

			{
				if (in(xx, yy)) {//枠内に入っているか
					if (retu[xx][yy] != 'X') {//入れるか
						if (isdigit(retu[xx][yy])) {//数字かどうか
							if (retu[xx][yy] - '0' <= h) {//今の自分で食えるかどうか
								que.x.push(xx); que.y.push(yy); retu[xx][yy] = '.'; //二回計算すると困るとか思ったけどよく考えるとバグるなこれ、後回し
								hp.push(h + 1); minuites.push(min + 1);
								nokori.push(nannko - 1);
							}
							else {
								if (!dp[xx][yy] || dp[xx][yy] < h) {
									que.x.push(xx); que.y.push(yy); hp.push(h); minuites.push(min + 1); nokori.push(nannko);
									dp[xx][yy] = h;
								}
							}
						}
						else {
							if (!dp[xx][yy] || dp[xx][yy] < h) {
								que.x.push(xx); que.y.push(yy); hp.push(h); minuites.push(min + 1); nokori.push(nannko);
								dp[xx][yy] = h;
							}
						}
					}
				}
			}
		}
		//beforex = nx; beforey = ny;
		//if (count >= n) { cout << min + 1 << endl; break; }
		//if (que.x.empty()) { cout << count << endl; }
	}
	//cout << min + 1 << endl;
	return 0;
}

Submission

Task問題 E - チーズ (Cheese)
User nameユーザ名 keidaroo
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2619 Byte
File nameファイル名
Exec time実行時間 149 ms
Memory usageメモリ使用量 9088 KB

Test case

Set

Set name Score得点 / Max score Cases
set01 20 / 20 data1
set02 20 / 20 data2
set03 20 / 20 data3
set04 20 / 20 data4
set05 20 / 20 data5

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
data1 AC 1 ms 256 KB
data2 AC 1 ms 384 KB
data3 AC 3 ms 768 KB
data4 AC 149 ms 7424 KB
data5 AC 85 ms 9088 KB