76分求助QAQ
查看原帖
76分求助QAQ
102028
初嫁QAQ楼主2020/5/23 17:57
# include <iostream>
# include <cstdio>
# include <queue>
using namespace std;
struct node{
	int x,y,z;
};
queue<node> q;
int n,m,x0,y0,e;
int tpx[31][3],tpy[31][3],sx[31];
int T[310][310];
char c[310][310];
bool vis[310][310];
int xx[4]={0,0,1,-1};
int yy[4]={1,-1,0,0};
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			T[i][j]=1515454414;
			cin>>c[i][j];
			if(c[i][j]=='@')	
				x0=i,y0=j;
			if(c[i][j]>='A'&&c[i][j]<='Z'){
				e=c[i][j]-'A'+1;
				tpx[e][++sx[e]]=i;
				tpy[e][sx[e]]=j;
			}
		}
	q.push((node){x0,y0,0});
	vis[x0][y0]=1;
	while(!q.empty()){
		node t=q.front();q.pop();
		int x=t.x,y=t.y,z=t.z;
		//printf("%d %d %d\n",x,y,z);
		//cout<<c[x][y]<<endl;
		if(c[x][y]=='='){
			cout<<z;
			return 0;
		}
		for(int i=0;i<4;i++){
			int x1=x+xx[i],y1=y+yy[i];
			if(x1>n||x1<1||y1>m||y1<1||vis[x1][y1]||T[x1][y1]<=z+1||c[x1][y1]=='#')
				continue;	
			if(c[x1][y1]>='A'&&c[x1][y1]<='Z'){
				e=c[x1][y1]-'A'+1;
				vis[x1][y1]=1;
				T[x1][y1]=z+1;
				if(x1==tpx[e][1])
					q.push((node){tpx[e][2],tpy[e][2],z+1});
				else
					q.push((node){tpx[e][1],tpy[e][1],z+1});
			}
			else{
				q.push((node){x1,y1,z+1});
				vis[x1][y1]=1;
				T[x1][y1]=z+1;
			}				
		}
	}
	return 0;
}

附样例2:

10 200
########################################################################################################################################################################################################
=.B####.#.##....#..###.#.#.#######Y#.#.##.####K..I###....####.#####.####.#.#.########.#...#F#####.##..####......#.##.#######..##.#.#######.#..###.#F......P###..##..##..#.###..###.#.####M.#.###.##.####
####.######.D######..#.#####S.####P#...##.##.##########.##.##.####.##...#########.#.##...#..J.#..#.#.#..######.#N####.##.###.....L####.L..#..#EE#..#.#..###.####..#####..#...Q#####.#####K..#.##.####..#
#######.#.#..#.#...###..##I...#####.#####.####..##.#####.#####..#####.##..#..####.#######.....#..##.#####.#####..#...###.....#####.#..#...#.#...G#...###...##...####.#####....#.##########....#####...##
######.#.#..###..##.##.##.#########.####.#.#.#.###.#.#.###..R##.#.####.####.#.#..####..###########.###.##.#.Q###.#.##.##..####..#####.##B###..#..##..#####.###...##..########.####.#.#..###.##J.##..#..#
##X...#.##...###..########...#.#.##.###......#####.#####.#A####.##.#.##.#..###.##..#####....######..#...####..##.#H..#O...###.##..##.####.#.#.##N.#.####.########..####.##.##..###########...##X#..#..##
#####.###..###.###.#####....##.####.####.#.#..#.#..###.###..###.#.#####..###.###...###.#####.####.##.###...#.#..###.#############.##.##..###.#G##.##..######..###.###.#.####.####.###.###.#..##...##.###
###A..##..#####..#..#.###.##...#YC#.#O...##.#..........######.###..#.#.####.###..#######....##..#.###.#..#..#...##.##M..#.#..#...#.##.####.##.#S####.###.##..#.#######.######.#D######.#..#......###..##
######R..#.###.##.#.#.##.###..######.##..#.##..#####..Z###..#H.#.####.#.#.#.#ZC##...#...#.....###.#..###...#####.###..##.####..##.#.##..#####.##########.#.#..#.#...####.####...###...##...#..###.#...@#
########################################################################################################################################################################################################

ans:75 我的没有输出qaq

2020/5/23 17:57
加载中...