Submission #101929

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

struct state
{
	int x, y;
	int mask;
	int cost;

	state(int xa, int ya, int ma, int ca)
	{
		x = xa;
		y = ya;
		mask = ma;
		cost = ca;
	}

	state() {} 
};

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

int H, W;
char in[31][31];
int bitc[256];
int ax[4] = {-1, 0, 0, 1};
int ay[4] = {0, 1, -1, 0};

char at(int x, int y)
{
	if(x<0 || y<0 || x>=H || y>=W) return '#';
	return in[x][y];
}

bool vis[30][30][256];
int bx, by, ex, ey;

int main()
{
	for(int i=0;i<256;i++){

		bitc[i] = 0;
		for(int j=0;j<8;j++) if(i&(1<<j)) ++bitc[i];
	}

	scanf("%d%d", &H, &W);
	for(int i=0;i<H;i++){
		scanf("%s", in[i]);
		for(int j=0;j<W;j++){
			if(in[i][j]=='^'){
				bx = i; by = j; in[i][j]='.';
			}else if(in[i][j]=='$'){
				ex = i; ey = j; in[i][j]='.';
			}
		}
	}

	priority_queue<state> Q;
	state tmp;
	
	for(int i=0;i<H;i++) for(int j=0;j<W;j++)
		for(int k=0;k<256;k++) vis[i][j][k] = false;
	Q.push(state(bx, by, 0, 0));

	while(!Q.empty()){
		tmp = Q.top(); Q.pop();
		if(vis[tmp.x][tmp.y][tmp.mask]) continue;
		vis[tmp.x][tmp.y][tmp.mask] = true;
		//printf("%d %d %d: %d\n", tmp.x, tmp.y, tmp.mask, tmp.cost);
		if(tmp.x == ex && tmp.y == ey){
			printf("%d\n", tmp.cost);
			return 0;
		}

		char iv = in[tmp.x][tmp.y];
		if(iv >= 'a' && iv <= 'z'){
			if(!(tmp.mask & (1<<(iv-'a')))){
				//enable
				Q.push(state(tmp.x, tmp.y, tmp.mask | (1<<(iv-'a')), tmp.cost + 1 + bitc[tmp.mask]));
			}
		}
		if(iv >= 'A' && iv <= 'Z'){
			if((tmp.mask & (1<<(iv-'A')))){
				//disable
				Q.push(state(tmp.x, tmp.y, tmp.mask ^ (1<<(iv-'a')), tmp.cost + 0));
			}
		}

		for(int i=0;i<4;i++){
			int x2=ax[i]+tmp.x, y2=ay[i]+tmp.y;
			if(at(x2, y2) == '#') continue;

			iv = in[x2][y2];
			if(iv >= 'A' && iv <= 'Z'){
				if(!(tmp.mask & (1<<(iv-'A')))) continue;
			}

			Q.push(state(x2, y2, tmp.mask, tmp.cost + 1 + bitc[tmp.mask]));
		}
	}

	puts("-1");
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
./Main.cpp:53: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result

Judge Result