蒟蒻求助!!!棋盘全玄学RE
查看原帖
蒟蒻求助!!!棋盘全玄学RE
258081
zhangjinyan楼主2020/10/7 15:52

样例全对,测试全部RE,下载测试点数据后发现输入输出也一样,求大佬看看

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x;
	int y;
	int c;
	bool magic;
}mp[101][101];
int m,n,ans=999999;
int vis[1010][1010];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool canvisit(int x,int y)
{
	return x>=1&&y>=1&&x<=m&&y<=m;
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++)
		{
			mp[i][j].x=i;
			mp[i][j].y=j;
			mp[i][j].c=-1;
			mp[i][j].magic=0;
			vis[i][j]=-1;
		}
	}
	for(int i=1;i<=n;i++)
	{	
		int u,y,z;
		cin>>u>>y>>z;
		mp[u][y].c=z;
	}
	queue<node> q;
	node cur;
	q.push(mp[1][1]);
	
	vis[1][1]=0;
	while(!q.empty())
	{
		cur=q.front();
		q.pop();
		//cout<<cur.x<<" "<<cur.y<<" "<<cur.c<<endl;
		if(vis[cur.x][cur.y]>=ans)
		{
			continue;
		}
		if(cur.x==m&&cur.y==m)
		{
			ans=min(vis[m][m],ans);
		}
		for(int i=0;i<=4;i++)
		{
			int nx=cur.x+dx[i];
			int ny=cur.y+dy[i];	
			//cout<<cur.x<<" "<<cur.y<<"->"<<nx<<" "<<ny<<endl;
			//system("pause");
			if(!canvisit(mp[nx][ny].x,mp[nx][ny].y)) continue; 
			if(mp[nx][ny].c==cur.c&&mp[nx][ny].c!=-1&&vis[nx][ny]==-1)
			{
				vis[nx][ny]=vis[cur.x][cur.y];
				mp[nx][ny].magic=0;
				q.push(mp[nx][ny]);
				//cout<<cur.x<<" "<<cur.y<<" "<<cur.c<<"同色"<<endl;
			}else
			{
				if(mp[nx][ny].c!=cur.c&&vis[nx][ny]==-1&&mp[nx][ny].c!=-1&&cur.c!=-1)
				{
					vis[nx][ny]=vis[cur.x][cur.y]+1;
					mp[nx][ny].magic=0;
					q.push(mp[nx][ny]);
					//cout<<cur.x<<" "<<cur.y<<" "<<cur.c<<"异色"<<endl;
				}else
				{
					if(mp[nx][ny].c==-1&&vis[nx][ny]==-1&&cur.c!=-1&&cur.magic==0)
					{
						vis[nx][ny]=vis[cur.x][cur.y]+2;
						mp[nx][ny].c=cur.c;
						mp[nx][ny].magic=1;
						q.push(mp[nx][ny]);
						//cout<<cur.x<<" "<<cur.y<<" "<<cur.c<<"施法"<<endl;
					}
				}
			}
		}
	}
	if(ans==99999999) cout<<-1;
	else cout<<ans;
	return 0;
}
2020/10/7 15:52
加载中...