蒟蒻求助,38分
查看原帖
蒟蒻求助,38分
255762
lyxleo楼主2020/7/6 18:39

拜托各位大佬帮我看看,我调试两天了,还是不能AC,这怎么了?

#include <bits/stdc++.h>
using namespace std;
struct pos{
	long long x,y,step;
	pos(long long xx=0,long long yy=0,long long stepp=0) :x(xx),y(yy),step(stepp){}
};
long long n,m,end_x,end_y,start_x,start_y;
long long _map[305][305];
bool vis[305][305];
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};


bool can_enter(pos wz){
	return (wz.x >= 1 && wz.x <= n && wz.y >= 1 && wz.y <=m && _map[wz.x][wz.y] != 1 && (!vis[wz.x][wz.y]));
}

pos sreach(pos wz){
	for(long long i=1;i<=n;++i){
		for(long long j=1;j<=m;++j){
            if(!(i==wz.x&&j==wz.y))//注意不能与原点相同
			{
				if(_map[i][j]==_map[wz.x][wz.y])//直接判断匹配
				{
					vis[i][j]=true;
					return pos(i,j,wz.step);
				}
			}
		}
	}
    return pos(-1,-1,wz.step);
}

void bfs(pos wz){
	queue <pos> q;
	q.push(wz);
	vis[wz.x][wz.y]=true;
	while(!q.empty()){
		pos top = q.front();
		q.pop();
		if(top.x == end_x && top.y == end_y){
			printf("%lld",top.step);
			exit(0);
		}
		if(_map[top.x][top.y] > 3){
			pos next = sreach(top);
			vis[next.x][next.y] = true;
			q.push(next);
			continue;
		}
		for(int k=0;k<4;++k){
			pos try_pos = pos(top.x + dx[k],top.y + dy[k],top.step + 1);
			if(can_enter(try_pos)){
				vis[try_pos.x][try_pos.y] = true;
				q.push(try_pos);
			}
		}
	}
}

int main(){
	scanf("%lld %lld",&n,&m);
	for(long long i=1;i<=n;++i){
		for(long long j=1;j<=m;++j){
			char c;
			cin>>c;
			if(c == '#'){
				_map[i][j]=1;
				continue;
			}
			if(c == '.'){
				_map[i][j]=2;
				continue;
			}
			if(c == '='){
				_map[i][j]=3;
				end_x=i;
				end_y=j;
				continue;
			}
			if(c == '@'){
				start_x=i;
				start_y=j;
			}
			else{//传送门,特殊处理 
				_map[i][j]=c-65+4;
			}
		}
	}
	bfs(pos(start_x,start_y,0));
	return 0;
}
2020/7/6 18:39
加载中...