求调 玄关 莫名RE 40pts
查看原帖
求调 玄关 莫名RE 40pts
772368
Wind_love楼主2024/12/26 19:30

rt

#include<bits/stdc++.h>
using namespace std;
int n,m;
char p[505][505],tot,head[5500005],d[5500005],vis[5500005];
struct node{
	int v,w,nxt;
}a[5500005];
void add(int u,int v,int w){
	a[++tot].v=v;
	a[tot].w=w;
	a[tot].nxt=head[u];
	head[u]=tot;
	return;
}
priority_queue<pair<int,int>> pq;
int dij(int s,int t){
	d[s]=0;
	pq.push(make_pair(-d[s],s));
	while(!pq.empty()){
		int tp=pq.top().second;pq.pop();
		if(vis[tp])continue;
		vis[tp]=1;
		for(int i=head[tp];i;i=a[i].nxt){
			int yp=a[i].v,z=a[i].w;
			if(d[yp]>d[tp]+z){
				d[yp]=d[tp]+z;
				pq.push(make_pair(-d[yp],yp));
			}
		}
	}
	return d[t];
}
int get_num(int i,int j){
	return (i-1)*m+j;
}
signed main(){
	while(cin>>n>>m){
		if(n==0&&m==0)return 0;
		memset(head,0,sizeof head);
		memset(vis,0,sizeof vis);
		memset(a,0,sizeof a);
		memset(d,0x3f,sizeof d);
		tot=0;
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>p[i][j];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(i+1<=n&&p[i][j]==p[i+1][j])add(get_num(i,j),get_num(i+1,j),0);
				else if(i+1<=n)add(get_num(i,j),get_num(i+1,j),1);
				if(j+1<=m&&p[i][j]==p[i][j+1])add(get_num(i,j),get_num(i,j+1),0);
				else if(j+1<=m)add(get_num(i,j),get_num(i,j+1),1);
				if(i-1>=1&&p[i][j]==p[i-1][j])add(get_num(i,j),get_num(i-1,j),0);
				else if(i-1>=1)add(get_num(i,j),get_num(i-1,j),1);
				if(j-1>=1&&p[i][j]==p[i][j-1])add(get_num(i,j),get_num(i,j-1),0);
				else if(j-1>=1)add(get_num(i,j),get_num(i,j-1),1);
			}
		}
		int sx,sy,ex,ey;
		cin>>sx>>sy>>ex>>ey;
		sx++,sy++,ex++,ey++;
		cout<<dij(get_num(sx,sy),get_num(ex,ey))<<"\n";
	}
	return 0;
}
2024/12/26 19:30
加载中...