提交记录

代码

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

struct point
{
	bool last=false;
	int lastcolor;
	int x,y;
	int money=0;
	point(int a=0,int b=0,int mon=0):x(a),y(b),money(mon){}
};

bool operator > (point a,point b)
{
	return a.money>b.money;
}

priority_queue <struct point,vector<struct point>,greater<struct point>> prique;
int m,n;
int sheet[120][120];
bool history[120][120];
int movex[4]={1,-1,0,0};
int movey[4]={0,0,1,-1};

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}

inline bool check(int x,int y)
{
	if (x<1||x>m||y<1||y>m)
	{
		return false;
	}
	if (history[x][y])
	{
		return false;
	}
	return true;
}

int bfs()
{
	while (!prique.empty())
	{
		struct point ap=prique.top();
		prique.pop();
		if (ap.x==m&&ap.y==m)
		{
			return ap.money;
		}
		for (int i=0;i<4;i++)
		{
			int nextx=ap.x+movex[i];
			int nexty=ap.y+movey[i];
			if (check(nextx,nexty))
			{
				struct point nextpoint=point();
				nextpoint.x=nextx;
				nextpoint.y=nexty;
				history[nextx][nexty]=true;
				if (ap.last)//上次买了路
				{
					if (sheet[nextx][nexty]==-1)
					{
						continue;
					}
					else
					{
						if (ap.lastcolor==sheet[nextx][nexty])
						{
							nextpoint.money=ap.money;
						}
						else
						{
							nextpoint.money=ap.money+1;
						}
						prique.push(nextpoint);
					}
				}
				else
				{
					if (sheet[nextx][nexty]==-1)
					{
						nextpoint.last=true;
						nextpoint.lastcolor=sheet[ap.x][ap.y];
						nextpoint.money=ap.money+2;
					}
					else
					{
						if (sheet[nextx][nexty]==sheet[ap.x][ap.y])
						{
							nextpoint.money=ap.money;
						}
						else
						{
							nextpoint.money=ap.money+1;
						}
					}
					prique.push(nextpoint);
				}
				//process this
			}
		}
	}
	return -1;
}

int main()
{
	m=read();
	n=read();
	memset(sheet,-1,sizeof(sheet));
	for (register int i=0;i<n;i++)
	{
		int x,y,c;
		x=read();
		y=read();
		c=read();
		sheet[x][y]=c;
	}
	struct point first=point(1,1,0);
	prique.push(first);
	history[1][1]=true;
	cout << bfs() <<endl;
	return 0;
}