社区讨论

求助!为什么只输出-1QAQ

P3956[NOIP 2017 普及组] 棋盘参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@loblq7pi
此快照首次捕获于
2023/10/29 23:04
2 年前
此快照最后确认于
2023/11/04 03:56
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int col[101][101];
struct bloc
{
	int x,y,color;
};
queue <bloc> q;
int f[101][101][2],dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};
bool vis[101][101][2];
int n,m;
void bfs()
{
	bloc xx;
	xx.x=xx.y=1,xx.color=col[1][1];
	f[1][1][col[1][1]]=0;
	q.push(xx);
	memset(vis,false,sizeof(vis));
	while (!q.empty())
	{
		bloc e=q.front(),s;
		q.pop();
		vis[e.x][e.y][e.color]=false;
		for (int i=0; i<4; i++)
		{
			s.x=e.x+dx[i],s.y=e.y+dy[i],s.color=col[s.x][s.y];
			if (s.x<1||s.x>n||s.y<1||s.y>n) continue;
			if (s.color==-1)
			{
				s.color=e.color;
				if (col[e.x][e.y]==-1) continue;
				if (f[e.x][e.y][e.color]+2<f[s.x][s.y][s.color]||f[s.x][s.y][s.color]==-1)
				{
					f[s.x][s.y][s.color]=f[e.x][e.y][e.color]+2;
					if (!vis[s.x][s.y][s.color])
					{
						vis[s.x][s.y][s.color]=true;
						q.push(s);
					}
				}
			}
			else
			{
				if (col[s.x][s.y]==e.color)
				{
					if (f[e.x][e.y][e.color]<f[s.x][s.y][s.color]||f[s.x][s.y][s.color]==-1)
					{
						f[s.x][s.y][s.color]=f[e.x][e.y][e.color];
						if (!vis[s.x][s.y][s.color])
						{
							vis[s.x][s.y][s.color]=true;
							q.push(s);
						}
					}
				}
				else
				{
					if (f[e.x][e.y][e.color]+1<f[s.x][s.y][s.color]||f[s.x][s.y][s.color]==-1)
					{
						f[s.x][s.y][s.color]=f[e.x][e.y][e.color]+1;
						if (!vis[s.x][s.y][s.color])
						{
							vis[s.x][s.y][s.color]=true;
							q.push(s);
						}
					}
				}
			}
			if (f[n][n][0]==-1 || f[n][n][1]==-1) cout << max(f[n][n][0],f[n][n][1]);
			else cout << min(f[n][n][0],f[n][n][1]);
			return;
		}
	}
}
int main()
{
	cin>>n>>m;
	memset(col,-1,sizeof(col));
	memset(f,-1,sizeof(f));
	for (int i=1; i<=m; i++)
	{
		int x,y;
		cin>>x>>y;
		cin>>col[x][y];
	}
	bfs();
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...