玄关 60分WA3,4 求调
查看原帖
玄关 60分WA3,4 求调
1121518
StarsIntoSea楼主2024/5/2 10:00
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<pair<int,int>> a[500000];
priority_queue<pair<int,int>> q;
char map[502][502];
int dis[500000],vis[500000];
int n,m,x1,y1,x2,y2,l,r;
int gum(int x,int y){
	return (x-1)*n+y;
}
int main(){
//	printf("%d\n",('@'!='#'));
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0&&m==0) break;
		for(int i=1;i<=gum(500,500);++i)
			a[i].clear();
		while(!q.empty()) q.pop();
		
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j){
				cin>>map[i][j];
				if(i>1){
					a[gum(i,j)].push_back(make_pair(gum(i-1,j),map[i][j]!=map[i-1][j]));
					a[gum(i-1,j)].push_back(make_pair(gum(i,j),map[i][j]!=map[i-1][j]));
				}
				if(j>1){
					a[gum(i,j)].push_back(make_pair(gum(i,j-1),map[i][j]!=map[i][j-1]));
					a[gum(i,j-1)].push_back(make_pair(gum(i,j),map[i][j]!=map[i][j-1]));
				}
			}
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		x1++,x2++,y1++,y2++;
		l=gum(x1,y1);
		r=gum(x2,y2);
		
		for(int i=1;i<=gum(n,m);++i)
			vis[i]=0,dis[i]=2e9;
		q.push(make_pair(0,l));
		dis[l]=0;
		while(!q.empty()){
			int x=q.top().second;
			q.pop();
			if(vis[x]) continue;
			vis[x]=1;
			for(int i=0;i<(int)a[x].size();++i){
				int t=a[x][i].first;
				int wei=a[x][i].second;
				if(dis[t]>dis[x]+wei){
					dis[t]=dis[x]+wei;
					q.push(make_pair(-dis[t],t));
				}
			}
		}
		
		printf("%d\n",dis[r]);
	}
}
2024/5/2 10:00
加载中...