Submission #101876

---

Source Code Expand

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>
#include <cstring>
using namespace std;

bool memo[30][30][1<<8];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

class State
{
public:
	int x,y,f,c;
	State(int x, int y, int c, int f)
		:x(x),y(y),c(c),f(f)
	{}

	bool operator<(const State& s) const {
		return c > s.c;
	}
};

int main()
{
	int W, H;
	memset(memo, 0, sizeof(memo));

	cin >> H >> W;
	vector<string> field(H);
	for(int i=0; i<H; i++) {
		cin >> field[i];
	}

	int sx, sy;
	for(int i=0; i<H; i++)
	for(int j=0; j<W; j++) {
		if(field[i][j] == '^') {
			sx = j;
			sy = i;
		}
	}

	priority_queue<State> q;
	q.push(State(sx, sy, 0, 0));

	int res = -1;
	while(!q.empty()) {
		State s = q.top(); q.pop();
		if(memo[s.x][s.y][s.f]) continue;
		memo[s.x][s.y][s.f] = 1;

		if(field[s.y][s.x] == '$') {
			res = s.c;
			break;
		}

		for(int i=0; i<4; i++) {
			int nx = s.x + dx[i];
			int ny = s.y + dy[i];
			int nc = s.c + 1 + __builtin_popcount(s.f);
			int nf = s.f;

			if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
			if(field[ny][nx] == '#') continue;
			char c = field[ny][nx];

			if(islower(c)) {
				q.push(State(nx, ny, nc, nf));
				q.push(State(nx, ny, nc + 1 + __builtin_popcount(s.f), nf | ( 1 << (c - 'a'))));
				
			}

			else if(isupper(field[ny][nx])) {
				if((nf >> (c - 'A')) & 1) {
					q.push(State(nx, ny, nc, nf));
					q.push(State(nx, ny, nc, nf ^ (1 << (c - 'A'))));
				}
			}

			else {
				q.push(State(nx, ny, nc, nf));
			}
		}
	}

	cout << res << endl;


		
	
}

Submission Info

Judge Result