萌新dij60分,求查错
查看原帖
萌新dij60分,求查错
342090
Lips楼主2020/7/3 17:17
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
const int SIZE=510;
const int MAXN=1000010;
int n,m,d[MAXN];
char maze[SIZE][SIZE];
struct edge
{
	int to,cost;
	edge(int to,int cost):to(to),cost(cost){}
};
vector<edge>G[MAXN];
typedef pair<int,int>P;
int getnum(int x,int y)
{
	return (x-1)*m+y;
}
void add_edge(int x1,int y1,int x2,int y2)
{
	int w=1;
	if(maze[x1][y1]==maze[x2][y2]) w=0;
	int u=getnum(x1,y1),v=getnum(x2,y2);
	G[u].push_back(edge(v,w));
	G[v].push_back(edge(u,w));
}
void dijkstra(int s)
{
	int end=getnum(n,m);
	priority_queue<P,vector<P>,greater<P> >q;
	for(register int i=1;i<=end;i++) d[i]=1e9;
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		P p=q.top();
		q.pop();
		int v=p.second;
		if(d[v]<p.first) continue;
		for(register int i=0;i<G[v].size();i++)
		{
			edge e=G[v][i];
			if(d[e.to]>d[v]+e.cost)
			{
				d[e.to]=d[v]+e.cost;
				q.push(make_pair(d[e.to],e.to));
			}
		}
	}
}
int main()
{
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0) return 0;
		for(register int i=1;i<=n;i++)
			for(register int j=1;j<=m;j++)
				cin>>maze[i][j];
		for(register int i=1;i<=n;i++)
			for(register int j=1;j<=n;j++)
				if(i==n&&j!=m) add_edge(i,j,i,j+1);
				else
					if(i<n&&j!=m) add_edge(i,j,i,j+1),add_edge(i,j,i+1,j);
					else if(i<n&&j==m) add_edge(i,j,i+1,j); 
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		int s=getnum(x1+1,y1+1),t=getnum(x2+1,y2+1);
		dijkstra(s);
		printf("%d\n",d[t]);
		int end=getnum(n,m);
		for(register int i=1;i<=end;i++) G[i].clear();
	}
}
2020/7/3 17:17
加载中...