萌新刚学 OI,求助 RE
查看原帖
萌新刚学 OI,求助 RE
548203
KK_lang楼主2023/8/1 13:10
#include<bits/stdc++.h>
using namespace std;

int n, p[10][10];
struct Node { int x, y, side; } dfsArray[1000010];

void Down()
{
	int t[10][10];
	for (int i = 1; i <= 5; i++)
		for (int j = 1; j <= p[i][0]; j++)
			if (p[i][j] != 0) t[i][++t[i][0]] = p[i][j];
	memcpy(p, t, sizeof(p));
}

bool Remove()
{
    int Remove[10][10];
    memcpy(Remove, p, sizeof(p));
    bool flag = false;
    for (int i = 1; i <= 5; i++) 
    	for (int j = 1; j <= p[i][0]; j++)
    	{
    		if (j > 1 && j < p[i][0] && p[i][j] != 0 && p[i][j] == p[i][j - 1] && p[i][j] == p[i][j + 1])
    			flag = true, Remove[i][j] = Remove[i][j - 1] = Remove[i][j + 1] = 0;
    		if (i > 1 && i < 5 && p[i][j] != 0 && p[i][j] == p[i - 1][j] && p[i - 1][j] == p[i + 1][j])
    			flag = true, Remove[i][j] = Remove[i - 1][j] = Remove[i][j - 1] = 0;
    	}
    memcpy(p, Remove, sizeof(p));
    return flag;
}

void dfs(int step)
{
	if (step > n)
	{
		for (int i = 1; i <= 5; i++)
			if (p[i][0] > 0) return;
		for (int i = 1; i <= step; i++)
    		cout << dfsArray[i].x - 1 << " " << dfsArray[i].y - 1 << " " << dfsArray[i].side << endl;
    	exit(0);
    }
	int t[10][10];
	memcpy(t, p, sizeof(p));
	for (int i = 1; i <= 5; i++)
		for (int j = 1; j <= p[i][0]; j++)
		{
			if (p[i][j] == 0) break;
			dfsArray[step].x = i, dfsArray[step].y = j;
			if (i < 5 && p[i][j] != p[i + 1][j])
			{
				dfsArray[step].side = 1;
				swap(p[i][j], p[i + 1][j]);
				Down();
				while (Remove()) Down();
				dfs(step + 1);
				memcpy(p, t, sizeof(p));
			}
			if (i > 1 && p[i][j] != p[i - 1][j])
			{
				dfsArray[step].side = -1;
				swap(p[i][j], p[i - 1][j]);
				Down();
				while (Remove()) Down();
				dfs(step + 1);
				memcpy(p, t, sizeof(p));
			}
		}
}

int main()
{
    cin >> n;
    for (int i = 1; i <= 5; i++)
    {
        int t;
        while (cin >> t && t) p[i][++p[i][0]] = t;
    }
    dfs(0);
    cout << -1 << endl;
    return 0;
}
2023/8/1 13:10
加载中...