Submission #101970

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
typedef pair<int,int> P;
priority_queue<P, vector<P>, greater<P> > pq;
int INF=1000000007;
int fld[35][35];
int minv[35][35][280];
int used[35][35][280];
int H,W;
char rds[99];
int st=0;
int gl=0;
int ln1=1000000;
int ln2=1000;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int main() {
	for(int i=0;i<35;i++) {
		for(int j=0;j<35;j++) {
			fld[i][j]=-1;
			for(int k=0;k<280;k++) {
				minv[i][j][k]=INF;
			}
		}
	}
	scanf("%d%d",&H,&W);
	for(int i=1;i<=H;i++) {
		scanf("%s",rds);
		for(int j=0;j<W;j++) {
			if(rds[j]=='^') {
				st=i*ln1+(j+1)*ln2;
				fld[i][j+1]=9;
			}
			if(rds[j]=='.') fld[i][j+1]=9;
			if(rds[j]=='$') {
				gl=i*ln1+(j+1)*ln2;
				fld[i][j+1]=9;
			}
			if(rds[j]>='a'&&rds[j]<='h') {
				fld[i][j+1]=(int)(rds[j]-'a');
			}
			if(rds[j]>='A'&&rds[j]<='H') {
				fld[i][j+1]=(int)(rds[j]-'A')+10;
			}
		}
	}
	pq.push(make_pair(0,st));
	while(pq.size()) {
		int v1=pq.top().first;
		int v2=pq.top().second;
		int h1=v2/ln1;
		int w1=(v2%ln1)/ln2;
		int k1=v2%ln2;
		pq.pop();
		if(used[h1][w1][k1]==0) {
			used[h1][w1][k1]=1;
			minv[h1][w1][k1]=v1;
			int cst=1;
			int vt=1;
			for(int i=0;i<8;i++) {
				if(k1&vt) cst++;
				vt+=vt;
			}
			for(int i=0;i<4;i++) {
				if(fld[h1+dx[i]][w1+dy[i]]>=0&&used[h1+dx[i]][w1+dy[i]][k1]==0) {
					if(fld[h1+dx[i]][w1+dy[i]]>=10) {
						if(k1&(1<<(fld[h1+dx[i]][w1+dy[i]]-10))) {
							vt=(h1+dx[i])*ln1;
							vt+=(w1+dy[i])*ln2;
							vt+=k1;
							pq.push(make_pair(v1+cst,vt));
						}
					} else {
						vt=(h1+dx[i])*ln1;
						vt+=(w1+dy[i])*ln2;
						vt+=k1;
						pq.push(make_pair(v1+cst,vt));
					}
				}
			}
			if(fld[h1][w1]<9) {
				if((k1&(1<<(fld[h1][w1])))==0) {
					vt=h1*ln1;
					vt+=w1*ln2;
					vt+=k1+(1<<(fld[h1][w1]));
					pq.push(make_pair(v1+cst,vt));
				}
			}
			int vvt=1;
			for(int i=0;i<8;i++) {
				if(k1&vvt) {
					vt=h1*ln1;
					vt+=w1*ln2;
					vt+=k1-vvt;
					pq.push(make_pair(v1,vt));
				}
				vvt+=vvt;
			}
		}
	}
	int gh=gl/ln1;
	int gw=(gl%ln1)/ln2;
	if(minv[gh][gw][0]<INF) {
		printf("%d\n",minv[gh][gw][0]);
	} else {
		printf("-1\n");
	}
	return 0;
}

Submission Info

Compile Error

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

Judge Result