WA38求调
查看原帖
WA38求调
29502
YangHao楼主2022/7/5 17:29
#include <cstdio>
#include <cstdlib>
#include <cstring>

const int MAXN=310;

int n, m;
char str[MAXN][MAXN];

struct point{
	int x, y;
	point() {
		x=y=0;
	}
	int change (){
		return x*301+y;
	}
}tp[30][3], oppo[MAXN*MAXN*10], q[MAXN*MAXN*10];
int tf[MAXN*MAXN]; //whether it is in the queue or not
int tplen[30];
struct edge{
	point st, ed;
	int next;
	edge(){
		next=0;
	}
	//print function for debug
	void print (int num){
		printf ("%d st %d %d  ed %d %d  next %d\n", num, st.x, st.y, ed.x, ed.y, next);
	}
}e[MAXN*MAXN*10];
int egnum=0;
int first[MAXN*MAXN];
int fx[6]={0, 0, 0, 1, -1};
int fy[6]={0, 1, -1, 0, 0};
point ST, ED; //start & target point
int ans[MAXN*MAXN];

int operator<(const point a, const point b){
	if (a.x!=b.x) return a.x<b.x?1:0;
	return a.y<=b.y?1:0;
}
//build an edge between p1 and p2
void connect (point p1, point p2){
	if (p1<p2) return;
	e[++egnum].st=p1; e[egnum].ed=p2; e[egnum].next=first[p1.change ()]; first[p1.change ()]=egnum;
	e[++egnum].st=p2; e[egnum].ed=p1; e[egnum].next=first[p2.change ()]; first[p2.change ()]=egnum;
}
void buildmap (){
	memset (first, 0, sizeof (first));
	memset (tplen, 0, sizeof (tplen));
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j){
			point pt; pt.x=i; pt.y=j;
			oppo[pt.change ()]=pt;
		}
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j){
			point p1; p1.x=i; p1.y=j;
			if ('A'<=str[i][j]&&'Z'>=str[i][j]){
				int tpnum=str[i][j]-'A'+1;
				tp[tpnum][++tplen[tpnum]]=p1;
				if (2==tplen[tpnum]){
					oppo[tp[tpnum][1].change ()]=tp[tpnum][2];
					oppo[tp[tpnum][2].change ()]=tp[tpnum][1];
				}
			}
		}
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j){
			point p1; p1.x=i; p1.y=j;
			if ('@'==str[i][j]){
				ST=p1; str[i][j]='.';
			}
			if ('='==str[i][j]){
				ED=p1; str[i][j]='.';
			}
			if ('.'==str[i][j]||('A'<=str[i][j]&&'Z'>=str[i][j]))
				for (int k=1; k<=4; ++k){
					int nx=i+fx[k], ny=j+fy[k];
					if (1>nx||1>ny||nx>n||ny>m) continue;
					if ('#'==str[nx][ny]) continue;
					point p2;
					p2.x=nx; p2.y=ny;
					connect (p1, oppo[p2.change ()]);
					if (oppo[p2.change ()].change ()!=p2.change ())
						connect (oppo[p2.change ()], p1);
				}
		}
}
void SPFA (){
//only for debug
//	for (int i=1; i<=egnum; ++i)
//		e[i].print (i);
//	for (int i=1; i<=MAXN*MAXN; ++i){
//		if (!oppo[i].change ()) continue;
//		if (first[i])
//			printf ("first[%d]=%d\n", i, first[i]);
//		if (oppo[i].change()!=i)
//			printf ("oppo[%d]=%d %d %d\n", i, oppo[i].x, oppo[i].y, oppo[i].change());
//	}
	memset (tf, 0, sizeof (tf));
	memset (ans, 63, sizeof (ans));
	int st=1, ed=2;
	q[st]=ST; ans[ST.change ()]=0;
	while (st<ed){
		int x=q[st].change ();
		for (int i=first[x]; i; i=e[i].next){
			int y=e[i].ed.change ();
			if (ans[y]>ans[x]+1){
				ans[y]=ans[x]+1;
				if (!tf[y]){
					tf[y]=1;
					q[ed++]=e[i].ed;
				}
			}
		}
		++st; tf[x]=0;
	}
}
int main(){
	scanf ("%d%d", &n, &m);
	for (int i=1; i<=n; ++i)
		scanf ("%s", str[i]+1);
	buildmap ();
	SPFA ();
	printf ("%d", ans[ED.change ()]);
}

RT,不知哪里错了,麻烦dalao看一看,谢谢!

2022/7/5 17:29
加载中...