Submission #1359274
Source Code Expand
#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 Info
Submission Time |
|
Task |
E - チーズ (Cheese) |
User |
keidaroo |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2619 Byte |
Status |
AC |
Exec Time |
149 ms |
Memory |
9088 KB |
Judge Result
Set Name |
set01 |
set02 |
set03 |
set04 |
set05 |
Score / Max Score |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
20 / 20 |
Status |
|
|
|
|
|
Set Name |
Test Cases |
set01 |
data1 |
set02 |
data2 |
set03 |
data3 |
set04 |
data4 |
set05 |
data5 |
Case Name |
Status |
Exec Time |
Memory |
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 |