求调
查看原帖
求调
939020
YC_Lyy楼主2024/11/24 20:26
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll ans, a, b, x, y, d1, d2;
ll dx[] = {-1, 0, 1, 0};
ll dy[] = {0, 1, 0, -1};
char p[100][100];
bool vis[160005];

struct edge {
	ll x, y;
};

void bfs()
{
	queue <edge> q;
	queue <edge> g;
	q.push({x, y});
	g.push({a, b});
	int w;
	while (! q.empty() && ! g.empty())
	{
		ll nowx1 = q.front().x;
		ll nowy1 = q.front().y;
		ll nowx2 = g.front().x;
		ll nowy2 = g.front().y;
		ll newx1 = nowx1 + dx[d1];
		ll newy1 = nowy1 + dy[d1];
		ll newx2 = nowx2 + dx[d2];
		ll newy2 = nowy2 + dy[d2];
		if (newx1 > 10 || newy1 > 10 || newx1 < 1 || newy1 < 1 || p[newx1][newy1] == '*')
		{
			d1 = (d1 + 1) % 4;
			if (newx2 > 10 || newy2 > 10 || newx2 < 1 || newy2 < 1 || p[newx2][newy2] == '*')
			{
				d2 = (d2 + 1) % 4;
				continue;
			}
			g.pop();
			g.push({newx2, newy2});
			if (nowx1 == newx2 && nowy1 == newy2)
				return;
			w = nowx1 + nowy1 * 10 + newx2 * 100 + newy2 * 1000 + d1 * 10000 + d2 * 10000;
		}
		if (newx2 > 10 || newy2 > 10 || newx2 < 1 || newy2 < 1 || p[newx2][newy2] == '*')
		{
			d2 = (d2 + 1) % 4;
			if (newx1 > 10 || newy1 > 10 || newx1 < 1 || newy1 < 1 || p[newx1][newy1] == '*')
			{
				d1 = (d1 + 1) % 4;
				continue;
			}
			q.pop();
			q.push({newx1, newy1});
			if (newx1 == nowx2 && newy1 == nowy2)
				return;
			w = newx1 + newy1 * 10 + nowx2 * 100 + nowy2 * 1000 + d1 * 10000 + d2 * 10000;
		}
		
		if (newx1 <= 10 && newy1 <= 10 && newx1 >= 1 && newy1 >= 1 && p[newx1][newy1] != '*' && newx2 <= 10 && newy2 <= 10 && newx2 >= 1 && newy2 >= 1 && p[newx2][newy2] != '*')
		{
			if (newx1 == newx2 && newy1 == newy2)
				return;
			q.pop();
			q.push({newx1, newy1});
			g.pop();
			g.push({newx2, newy2});
		}
		
		if (vis[w] == 1 && ans >= 1)
		{
			ans = 0;
			return;
		}
		vis[w] = 1;
		ans++;
	}
}

int main()
{
	for (ll i = 1; i <= 10; i++)
		for (ll j = 1; j <= 10; j++)
		{
			cin >> p[i][j];
			if (p[i][j] == 'C')
			{
				a = i;
				b = j;
			}
			if (p[i][j] == 'F')
			{
				x = i;
				y = j;
			}
		}
	int w = x + y * 10 + a * 100 + b * 1000 + d1 * 10000 + d2 * 10000;
	vis[w] = 1;
	bfs();
	printf("%lld\n", ans);
    return 0;
}

2024/11/24 20:26
加载中...