AtCoder Beginner Contest 184 E - Third Avenue (BFS)

题意:给你一张图,\(S\)表示起点,\(G\)表示终点,\(.\)表示可以走,#表示不能走,小写字母可以传送到任意一个相同的字母的位置,问从\(S\)走到\(G\)的最小步数.
题解:假如不考虑字母的话,就是一个经典的bfs,当我们走到字母时,将其它相同字母的位置入队,之后就不会再将它们入队了,因为之后走到这个字母的步数一定大于第一次传送的步数,所以我们可以先记录每个字母的位置,然后跑个bfs即可.
代码:

struct misaka{

	int x,y;

	int cnt;

}e[N];

int n,m;

char s[2100][2100];

bool st[2100][2100];

vector<PII> v[30];

PII stt;

const int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};

bool c[30];

void bfs(){

	queue<misaka> q;

	q.push({stt.fi,stt.se,0});

	bool flag=false;

	while(!q.empty()){

		auto tmp=q.front();

		q.pop();

		int x=tmp.x;

		int y=tmp.y;

		int cnt=tmp.cnt;

		if(st[x][y]) continue;

		st[x][y]=true;

		if(s[x][y]=='G'){

			flag=true;

			cout<<cnt;

			break;

		}

		if(s[x][y]>='a' && s[x][y]<='z' && !c[s[x][y]-'a']){

			for(auto w : v[s[x][y]-'a']){

				q.push({w.fi,w.se,cnt+1});

				c[s[x][y]-'a']=true;

			}

		}

		rep(i,0,3){

			int tx=x+dx[i];

			int ty=y+dy[i];

			if(tx<1 || tx>n || ty<1 || ty>m) continue;

			if(tx>=1 && tx<=n && ty>=1 && ty<=m && s[tx][ty]!='#' && !st[tx][ty] && !c[s[tx][ty]-'a']){

				q.push({tx,ty,cnt+1});

			}

		}

	}

	if(!flag) cout<<-1;

}

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n>>m;

	rep(i,1,n){

		rep(j,1,m){

			cin>>s[i][j];

			if(s[i][j]=='S') stt={i,j};

			if(s[i][j]>='a' && s[i][j]<='z') v[s[i][j]-'a'].pb({i,j});

		}

	}

	bfs();

    return 0;

}

巴特西

AtCoder Beginner Contest 184 E - Third Avenue (BFS)

最新文章

热门文章