和标程对拍100+最大随机数据全部通过然而爆零求助
查看原帖
和标程对拍100+最大随机数据全部通过然而爆零求助
113495
瓦特Water楼主2020/12/2 19:01

QAQ

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int read()
{
	int num = 0; char c = getchar();
	while (c < '0' || c>'9') c = getchar();
	while (c >= '0' && c <= '9')
	{
		num = (num << 1) + (num << 3) + (c ^ '0');
		c = getchar();
	}
	return num;
}
int mmp[510][510];
int dis[510][510];
int x1, x2, ys, ye;
struct node
{
	int x;
	int y;
	bool operator ==(node b)
	{
		return mmp[x][y] != mmp[b.x][b.y];
	}
	node(int x3, int y3)
	{
		x = x3; y = y3;
	}
};
queue <node> que;
int m, n;
void cmp()
{
	dis[x1][ys] = 0;
	que.push(node( x1,ys ));
	while (!que.empty())
	{
		node p = que.front();
		que.pop();
		if (p.x > 0)
		{
			node l( p.x - 1,p.y );
			if (dis[l.x][l.y] > dis[p.x][p.y] + (p == l))
			{
				dis[l.x][l.y] = dis[p.x][p.y] + (p == l);
				que.push(l);
			}
		}
		if (p.y > 0)
		{
			node l( p.x,p.y - 1 );
			if (dis[l.x][l.y] > dis[p.x][p.y] + (p == l))
			{
				dis[l.x][l.y] = dis[p.x][p.y] + (p == l);
				que.push(l);
			}
		}
		if (p.x < n - 1)
		{
			node l( p.x + 1,p.y );
			if (dis[l.x][l.y] > dis[p.x][p.y] + (p == l))
			{
				dis[l.x][l.y] = dis[p.x][p.y] + (p == l);
				que.push(l);
			}
		}
		if (p.y < m - 1)
		{
			node l( p.x,p.y + 1 );
			if (dis[l.x][l.y] > dis[p.x][p.y] + (p == l))
			{
				dis[l.x][l.y] = dis[p.x][p.y] + (p == l);
				que.push(l);
			}
		}
	}
}
int main()
{
	while (1)
	{
		n = read(); m = read();
		if (n == 0 || m == 0) break;
		memset(mmp, 0, sizeof mmp);
		memset(dis, 0x3f, sizeof dis);
		char c = '\n';
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				while (c == '\n') c = getchar();
				mmp[i][j] = (c == '#' ? 1 : 0);
				c = getchar();
			}
		}
		x1 = read(); ys = read(); x2 = read(); ye = read();
		cmp();
		printf("%d\n", dis[x2][ye]);
	}
	return 0;
}
2020/12/2 19:01
加载中...