P1518 44pts求解
  • 板块学术版
  • 楼主happybob
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/3/20 21:56
  • 上次更新2023/11/5 01:49:15
查看原帖
P1518 44pts求解
332914
happybob楼主2021/3/20 21:56
#include <iostream>
#include <algorithm>
using namespace std;

char ch[15][15];

struct Node
{
	int x, y;
	int fw;
	int c;
};

int cnt = 0;

Node a[15][15];

void dfs(int fx, int fy, int cx, int cy)
{
	cnt++;
	if (a[fx][fy].fw == 1)
	{
		if (fx - 1 <= 0 || a[fx - 1][fy].c == 4)
		{
			a[fx][fy].fw++;
			a[fx][fy].fw--;
			a[fx][fy].fw %= 4;
			a[fx][fy].fw++;
		}
		else
		{
			swap(a[fx - 1][fy], a[fx][fy]);
			fx--;
		}
	}
	else if (a[fx][fy].fw == 2)
	{
		if (fy + 1 > 10 || a[fx][fy + 1].c == 4)
		{
			a[fx][fy].fw++;
			a[fx][fy].fw--;
			a[fx][fy].fw %= 4;
			a[fx][fy].fw++;
		}
		else
		{
			swap(a[fx][fy + 1], a[fx][fy]);
			fy++;
		}
	}
	else if (a[fx][fy].fw == 3)
	{
		if (fx + 1 > 10 || a[fx + 1][fy].c == 4)
		{
			a[fx][fy].fw++;
			a[fx][fy].fw--;
			a[fx][fy].fw %= 4;
			a[fx][fy].fw++;
		}
		else
		{
			swap(a[fx + 1][fy], a[fx][fy]);
			fx++;
		}
	}
	else if (a[fx][fy].fw == 4)
	{
		if (fy - 1 <= 0 || a[fx][fy - 1].c == 4)
		{
			a[fx][fy].fw++;
			a[fx][fy].fw--;
			a[fx][fy].fw %= 4;
			a[fx][fy].fw++;
		}
		else
		{
			swap(a[fx][fy - 1], a[fx][fy]);
			fy--;
		}
	}
	if (a[cx][cy].fw == 1)
	{
		if (cx - 1 <= 0 || a[cx - 1][cy].c == 4)
		{
			a[cx][cy].fw++;
			a[cx][cy].fw--;
			a[cx][cy].fw %= 4;
			a[cx][cy].fw++;
		}
		else
		{
			swap(a[cx - 1][cy], a[cx][cy]);
			cx--;
		}
	}
	else if (a[cx][cy].fw == 2)
	{
		if (cy + 1 > 10 || a[cx][cy + 1].c == 4)
		{
			a[cx][cy].fw++;
			a[cx][cy].fw--;
			a[cx][cy].fw %= 4;
			a[cx][cy].fw++;
		}
		else
		{
			swap(a[cx][cy + 1], a[cx][cy]);
			cy++;
		}
	}
	else if (a[cx][cy].fw == 3)
	{
		if (cx + 1 > 10 || a[cx + 1][cy].c == 4)
		{
			a[cx][cy].fw++;
			a[cx][cy].fw--;
			a[cx][cy].fw %= 4;
			a[cx][cy].fw++;
		}
		else
		{
			swap(a[cx + 1][cy], a[cx][cy]);
			cx++;
		}
	}
	else if (a[fx][fy].fw == 4)
	{
		if (cy - 1 <= 0 || a[cx][cy - 1].c == 4)
		{
			a[cx][cy].fw++;
			a[cx][cy].fw--;
			a[cx][cy].fw %= 4;
			a[cx][cy].fw++;
		}
		else
		{
			swap(a[cx][cy - 1], a[cx][cy]);
			cy--;
		}
	}
	if (cnt > 1600000)
	{
		cnt = 0;
		return;
	}
	if (fx == cx && fy == cy)
	{
		return;
	}
	dfs(fx, fy, cx, cy);
}

int main()
{
	int fx, fy, cx, cy;
	fx = fy = cx = cy = 0;
	for (register int i = 1; i <= 10; i++)
	{
		for (register int j = 1; j <= 10; j++)
		{
			cin >> ch[i][j];
			a[i][j].x = i;
			a[i][j].y = j;
			if (ch[i][j] == 'C' || ch[i][j] == 'F')
			{
				a[i][j].fw = 1;
			}
			else
			{
				a[i][j].fw = 0;
			}
			if (ch[i][j] == 'C')
			{
				a[i][j].c = 1;
				cx = i;
				cy = j;
			}
			else if (ch[i][j] == 'F')
			{
				a[i][j].c = 2;
				fx = i;
				fy = j;
			}
			else if (ch[i][j] == '.') a[i][j].c = 3;
			else a[i][j].c = 4;
		}
	}
	dfs(fx, fy, cx, cy);
	cout << cnt << endl;
	return 0;
}
2021/3/20 21:56
加载中...