PCK過去問（会津の埋蔵金）

Algorithm

大変に下らないミスをしてけっこう時間かかった。

  • 入力はどんなに自明な場合でも最後まで読みましょう

わりとシンプルに実装できた気がする。
本選のとき通らなかったのは右いったり左いったりが複数回あるときの可能性を無視したてめという可能性が大。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

int W, H, F, M, O, mp[10][10];
bool visited[10][10][10][10][51];

struct state
{
	int left, right, pos;
	int depth, oxygen;
	int cost;
};

inline bool operator<(const state& a, const state& b)
{
	return a.cost > b.cost;
}

bool& vis(state& st)
{
	return visited[st.left][st.right][st.pos][st.depth][st.oxygen];
}

int main()
{
	for(;;){
		scanf("%d%d", &W, &H);
		if(W==0) break;
		scanf("%d%d%d", &F, &M, &O);

		for(int i=0;i<H;i++){
			for(int j=0;j<W;j++) scanf("%d", &(mp[i][j]));
		}

		if(O<=1){
			puts("NA");
			continue;
		}

		memset(visited, false, sizeof(visited));

		priority_queue<state> q;
		state st1, st2;

		for(int i=0;i<W;i++){
			st1.left = st1.right = st1.pos = i;
			st1.depth = 0; st1.oxygen = min(M, O - 1 + max(0, mp[0][i]));
			st1.cost = max(0, -mp[0][i]);

			q.push(st1);
		}

		int ret = F+1;
		while(!q.empty()){
			st1 = q.top(); q.pop();

			if(st1.depth==H-1 && st1.oxygen > 0){
				ret = st1.cost;
				break;
			}

			if(st1.oxygen <= 1 || vis(st1)) continue;
			vis(st1) = true;

			if(st1.pos!=0){
				//move left;

				st2 = st1;
				st2.pos = st1.pos - 1;
				st2.oxygen -= 1;
				if(st2.pos < st2.left){ //cost / oxygen
					st2.oxygen += max(0, mp[st2.depth][st2.pos]);
					st2.oxygen = min(st2.oxygen, M);
					st2.cost += max(0, -mp[st2.depth][st2.pos]);
					st2.left -= 1;
				}

				q.push(st2);
			}

			if(st1.pos!=W-1){
				//move right;

				st2 = st1;
				st2.pos = st1.pos + 1;
				st2.oxygen -= 1;
				if(st2.right < st2.pos){ //cost / oxygen
					st2.oxygen += max(0, mp[st2.depth][st2.pos]);
					st2.oxygen = min(st2.oxygen, M);
					st2.cost += max(0, -mp[st2.depth][st2.pos]);
					st2.right += 1;
				}

				q.push(st2);
			}

			//move down;
			st2 = st1;
			st2.left = st2.right = st2.pos;
			st2.depth += 1;
			st2.oxygen -= 1;
			st2.oxygen += max(0, mp[st2.depth][st2.pos]);
			st2.oxygen = min(st2.oxygen, M);
			st2.cost += max(0, -mp[st2.depth][st2.pos]);
			
			q.push(st2);
		}

		if(ret>F) puts("NA");
		else printf("%d\n", ret);
	}

	return 0;
}