1 条题解

  • 0
    @ 2026-3-19 1:04:03

    作为全网首 A，来一发题解。
    ac 记录：https://loj.ac/s/2484761

    思路

    前置知识：数字华容道。（不会的建议上网搜索，应该有一大堆教学）

    看上去很华容道，于是考虑把初始状态变为样例二那样的规则图案。具体来说，所有的棋子都在 (2x−1,2y−1)(2x-1,2y-1) 的坐标上，且所有棋子构成了一个左上方的阶梯状。又由于操作是可逆的，所以初始与终止局面都可以变为这样的规则图案。
    这个其实不难，对于所有棋子，尽量往左上移动就是对的。实现方面可以 while(true) 一下，直到没有任何一个棋子是可移动的。

    于是现在等价于有若干 2×22×2 的大块，每个大块的左上角有一个棋子。对大块跑华容道即可，因为显然这个过程不会使得合法状态变得不合法。接下来要稍微分讨一下：

    • 没有空的大块：华容道无法移动，直接特判掉。
    • 空的大块恰好一个：实现一下华容道的过程即可。
    • 空的大块多余一个：显然必然有解。为了实现方便，可以先只保留一个空块跑华容道，最后右下角的 2×22\times2 中一定包含至少两个空块，于是一定可移动。

    有一个特殊 case 需要判一下：如果 nn 为偶数且恰好只有一个空块，那么必然有解。原因是说，如果华容道跑出来无解，可以通过以下手段实现交换：

    1.3.          1...          1...          1.2.
....   --->   ....   --->   ..2.   --->   ....
2...   --->   .2..   --->   ....   --->   3...
....          ...3          ...3          ....

    正常的实现都应该不会被卡步数。

    实现

    主要讲一下华容道部分。记录一下空块的位置 (px,py)(px,py)，主要封装了以下函数：

    • work(x1,y1,x2,y2)：将 (x1,y1)(x1,y1) 的块移动到 (x2,y2)(x2,y2) 上。
    • move(x,y)：将空块移动到 (x,y)(x,y) 的相邻位置。
    • left/right/up/down(x,y)：将块 (x,y)(x,y) 向左/右/上/下移动。

    这几个函数可以使用一点 AI 辅助编程。
    需要注意的是，复原新的块时不要把已经复原好的块打乱了。

    建议是先把华容道部分调对再去写其他部分。

    #include<bits/stdc++.h>
using namespace std;
#define AI3 array<int, 3>

const int N = 110;
int n, m, k, a[N][N], b[N][N], id[N * N], c[N][N];
vector<AI3> s1, s2;
int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

inline void work(int x1, int y1, int x2, int y2)
{
	if(!a[x1][y1]) return;
	while(x1 < x2)
	{
		a[x1 + 1][y1] = a[x1][y1], a[x1][y1] = 0, x1++;
		s1.push_back({a[x1][y1], x1, y1});
	}
	while(x1 > x2)
	{
		a[x1 - 1][y1] = a[x1][y1], a[x1][y1] = 0, x1--;
		s1.push_back({a[x1][y1], x1, y1});
	}
	while(y1 < y2)
	{
		a[x1][y1 + 1] = a[x1][y1], a[x1][y1] = 0, y1++;
		s1.push_back({a[x1][y1], x1, y1});
	}
	while(y1 > y2)
	{
		a[x1][y1 - 1] = a[x1][y1], a[x1][y1] = 0, y1--;
		s1.push_back({a[x1][y1], x1, y1});
	}
}
inline void work1(int x1, int y1, int x2, int y2)
{
	swap(c[x1][y1], c[x2][y2]);
	work(2 * x1 - 1, 2 * y1 - 1, 2 * x2 - 1, 2 * y2 - 1);
}

int px, py;
inline void move(int x, int y)
{
	while(px < x) 
	{
		if(px + 1 == x && py == y) return;
		work1(px + 1, py, px, py), px++;
	}
	while(py < y) 
	{
		if(py + 1 == y && px == x) return;
		work1(px, py + 1, px, py), py++;
	}
	while(px > x) 
	{
		if(px - 1 == x && py == y) return;
		work1(px - 1, py, px, py), px--;
	}
	while(py > y) 
	{
		if(py - 1 == y && px == x) return;
		work1(px, py - 1, px, py), py--;
	}
}

inline void left(int x, int y)
{
	move(x, y);
	if(py == y + 1)
	{
		if(x == m) 
		{
			work1(x - 1, y + 1, x, y + 1);
			work1(x - 1, y, x - 1, y + 1);
			px = x - 1, py = y;
		}
		else
		{
			work1(x + 1, y + 1, x, y + 1);
			work1(x + 1, y, x + 1, y + 1);
			px = x + 1, py = y;
		}
	}
	if(px == x - 1)
	{
		work1(x - 1, y - 1, x - 1, y);
		work1(x, y - 1, x - 1, y - 1);
		px = x, py = y - 1;
	}
	if(px == x + 1)
	{
		work1(x + 1, y - 1, x + 1, y);
		work1(x, y - 1, x + 1, y - 1);
		px = x, py = y - 1;
	}
	work1(x, y, x, y - 1);
	px = x, py = y;
}

inline void right(int x, int y)
{	
	move(x, y);
	if(py == y - 1)
	{
		if(x == m) 
		{
			work1(x - 1, y - 1, x, y - 1);
			work1(x - 1, y, x - 1, y - 1);
			px = x - 1, py = y;
		}
		else
		{
			work1(x + 1, y - 1, x, y - 1);
			work1(x + 1, y, x + 1, y - 1);
			px = x + 1, py = y;
		}
	}
	if(px == x - 1)
	{
		work1(x - 1, y + 1, x - 1, y);
		work1(x, y + 1, x - 1, y + 1);
		px = x, py = y + 1;
	}
	if(px == x + 1)
	{
		work1(x + 1, y + 1, x + 1, y);
		work1(x, y + 1, x + 1, y + 1);
		px = x, py = y + 1;
	}
	work1(x, y, x, y + 1);
	px = x, py = y;
}

inline void up(int x, int y)
{
	move(x, y);
	if(px == x + 1)
	{
		if(y == m)
		{
			work1(x + 1, y - 1, x + 1, y);
			work1(x, y - 1, x + 1, y - 1);
			px = x, py = y - 1;
		}
		else
		{
			work1(x + 1, y + 1, x + 1, y);
			work1(x, y + 1, x + 1, y + 1);
			px = x, py = y + 1;
		}
	}
	if(py == y - 1)
	{
		work1(x - 1, y - 1, x, y - 1);
		work1(x - 1, y, x - 1, y - 1);
		px = x - 1, py = y;
	}
	if(py == y + 1)
	{
		work1(x - 1, y + 1, x, y + 1);
		work1(x - 1, y, x - 1, y + 1);
		px = x - 1, py = y;
	}
	work1(x, y, x - 1, y);
	px = x, py = y;
}

inline void down(int x, int y)
{
	move(x, y);
	if(px == x - 1)
	{
		if(y == m)
		{
			work1(x - 1, y - 1, x - 1, y);
			work1(x, y - 1, x - 1, y - 1);
			px = x, py = y - 1;
		}
		else
		{
			work1(x - 1, y + 1, x - 1, y);
			work1(x, y + 1, x - 1, y + 1);
			px = x, py = y + 1;
		}
	}
	if(py == y - 1)
	{
		work1(x + 1, y - 1, x, y - 1);
		work1(x + 1, y, x + 1, y - 1);
		px = x + 1, py = y;
	}
	if(py == y + 1)
	{
		work1(x + 1, y + 1, x, y + 1);
		work1(x + 1, y, x + 1, y + 1);
		px = x + 1, py = y;
	}
	work1(x, y, x + 1, y);
	px = x, py = y;
}

inline void getpos(int &x, int &y, int d)
{
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= m; j++)
			if(c[i][j] == d)
			{
				x = i, y = j;
				return;
			}
}

void out()
{
	printf("TAK\n%d\n", s1.size() + s2.size());
	for(AI3 i : s1) printf("%d %d %d\n", i[0], i[1], i[2]);
	reverse(s2.begin(), s2.end());
	for(AI3 i : s2) printf("%d %d %d\n", i[0], i[1], i[2]);
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
    	for(int j = 1; j <= n; j++)
    		scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; i++)
    	for(int j = 1; j <= n; j++)
    		scanf("%d", &b[i][j]);
    while(1)
    {
    	bool vis = 0;
	    for(int i = 1; i <= n; i++)
	    	for(int j = 1; j <= n; j++)
	    		if(a[i][j])
	    		{
	    			int x = i, y = j;
	    			while(1)
	    			{
	    				if(x > 1)
	    				{
	    					bool flag = 1;
	    					for(int k = 0; k <= 8 && flag; k++)
	    						if(k != 7)
	    						{
	    							int x1 = x - 1 + dx[k], y1 = y + dy[k];
	    							if(a[x1][y1]) flag = 0;
	    						}
	    					if(flag)
	    					{
	    						a[x - 1][y] = a[x][y], a[x][y] = 0, x--;
	    						s1.push_back({a[x][y], x, y});
	    						vis = 1;
	    						continue;
	    					}
	    				}
	    				if(y > 1)
	    				{
	    					bool flag = 1;
	    					for(int k = 0; k <= 8 && flag; k++)
	    						if(k != 5)
	    						{
	    							int x1 = x + dx[k], y1 = y - 1 + dy[k];
	    							if(a[x1][y1]) flag = 0;
	    						}
	    					if(flag)
	    					{
	    						a[x][y - 1] = a[x][y], a[x][y] = 0, y--;
	    						s1.push_back({a[x][y], x, y});
	    						vis = 1;
	    						continue;
	    					}
	    				}
	    				break;
	    			}
	    		}
	    if(!vis) break;
    }
    while(1)
    {
    	bool vis = 0;
	    for(int i = 1; i <= n; i++)
	    	for(int j = 1; j <= n; j++)
	    		if(b[i][j])
	    		{
	    			int x = i, y = j;
	    			while(1)
	    			{
	    				if(x > 1)
	    				{
	    					bool flag = 1;
	    					for(int k = 0; k <= 8 && flag; k++)
	    						if(k != 7)
	    						{
	    							int x1 = x - 1 + dx[k], y1 = y + dy[k];
	    							if(b[x1][y1]) flag = 0;
	    						}
	    					if(flag)
	    					{
	    						s2.push_back({b[x][y], x, y});
	    						b[x - 1][y] = b[x][y], b[x][y] = 0, x--;
	    						vis = 1;
	    						continue;
	    					}
	    				}
	    				if(y > 1)
	    				{
	    					bool flag = 1;
	    					for(int k = 0; k <= 8 && flag; k++)
	    						if(k != 5)
	    						{
	    							int x1 = x + dx[k], y1 = y - 1 + dy[k];
	    							if(b[x1][y1]) flag = 0;
	    						}
	    					if(flag)
	    					{
	    						s2.push_back({b[x][y], x, y});
	    						b[x][y - 1] = b[x][y], b[x][y] = 0, y--;
	    						vis = 1;
	    						continue;
	    					}
	    				}
	    				break;
	    			}
	    		}
	   	if(!vis) break;
    }

    m = n + 1 >> 1;
    vector<int> num, pos;
    for(int i = 1; i <= m; i++)
    	for(int j = 1; j <= m; j++)
    		if(b[2 * i - 1][2 * j - 1])
    			id[b[2 * i - 1][2 * j - 1]] = (i - 1) * m + j;
    		else num.push_back((i - 1) * m + j);
    for(int i = 1; i <= m; i++)
    	for(int j = 1; j <= m; j++)
    		if(a[2 * i - 1][2 * j - 1])
    			c[i][j] = id[a[2 * i - 1][2 * j - 1]];
    		else pos.push_back((i - 1) * m + j);
    if(pos.empty())
    {
		for(int i = 1; i <= n; i++)
    		for(int j = 1; j <= n; j++)
    			if(a[i][j] != b[i][j])
    				return puts("NIE"), 0;
    	return out(), 0;
    }

    for(int i = 0; i < pos.size() - 1; i++)
    {
    	int x = (pos[i] - 1) / m + 1, y = (pos[i] - 1) % m + 1;
    	c[x][y] = num[i];
    }
    //begin
    px = m, py = m;
    for(int i = 1; i <= m - 2; i++)
    {
    	for(int j = 1; j <= m - 1; j++)
    	{
    		int x, y;
    		getpos(x, y, (i - 1) * m + j);
    		while(y < j) right(x, y), y++;
    		while(y > j) left(x, y), y--;
    		move(x, y);
    		if(px == x && py == y - 1 && px == i + 1) up(x + 1, y - 1), left(x + 1, y);
    		while(x > i) up(x, y), x--;
    	}
    	if(!c[i][m]) up(i + 1, m);
    	if(c[i][m] == i * m) continue;
    	down(i, m), right(i, m - 1);
    	if(c[i + 1][m - 1] == i * m)
    	{
    		left(i, m), up(i + 1, m), up(i + 2, m), right(i + 2, m - 1);
    		down(i + 1, m - 1), left(i + 1, m), down(i, m), right(i, m - 1);
    		up(i + 1, m - 1), up(i + 2, m - 1), left(i + 2, m), down(i + 1, m);
    		right(i + 1, m - 1), down(i, m - 1), left(i, m), up(i + 1, m);
    	}
    	else
    	{
    		up(i + 1, m - 1);
    		int x, y;
    		getpos(x, y, i * m);
    		while(y < m) right(x, y), y++;
    		while(x > i + 1) up(x, y), x--;
    		if(py == m) right(px, py - 1);
    		down(i, m - 1), left(i, m), up(i + 1, m);
    	}
    }

    for(int i = 1; i <= m - 2; i++)
    {
		int x, y;
		getpos(x, y, (m - 2) * m + i);
		if(x == m - 1) down(x, y), x++;
		while(y > i) left(x, y), y--;

    	if(!c[m - 1][i]) left(m - 1, i + 1);
    	if(c[m - 1][i] == (m - 1) * m + i)
    	{
    		right(m - 1, i), up(m, i), left(m, i + 1), down(m - 1, i + 1);
    		left(m - 1, i + 2), up(m, i + 2), right(m, i + 1), right(m, i);
    		down(m - 1, i), left(m - 1, i + 1), up(m, i + 1), left(m, i + 2);
    		down(m - 1, i + 2), right(m - 1, i + 1), right(m - 1, i), up(m, i), left(m, i + 1);
    	}
    	else
    	{
			getpos(x, y, (m - 1) * m + i);
			if(x == m - 1) down(x, y), x++;
			while(y > i + 1) left(x, y), y--;
			if(px == m) down(px - 1, py);
			while(py > i) right(px, py - 1);
			up(m, i), left(m, i + 1);
    	}
    }
    int x, y;
    getpos(x, y, (m - 1) * m - 1);
    if(x == m) up(x, y), x--;
    if(y == m) left(x, y), y--;
    if(!c[m - 1][m]) up(m, m);
    if(!c[m][m - 1]) left(m, m);
    //end

    if(a[2 * m - 3][2 * m - 1] == b[2 * m - 3][2 * m - 1]) return out(), 0;
    if(!a[2 * m - 3][2 * m - 1])
    {
    	work1(m, m - 1, m, m), work1(m, m, m - 1, m);
    	return out(), 0;
    }
    if(!a[2 * m - 1][2 * m - 3])
    {
    	work1(m - 1, m, m, m), work1(m, m, m, m - 1);
    	return out(), 0;
    }
    if(n & 1) return puts("NIE"), 0;
    work(n - 3, n - 1, n, n), work(n - 1, n - 3, n - 1, n - 2);
    s1.push_back({a[n - 1][n - 2], n - 2, n - 1}), swap(a[n - 1][n - 2], a[n - 2][n - 1]);
    work(n - 2, n - 1, n - 3, n - 1), work(n, n, n - 1, n - 3);
    out();
    cerr << "\ntimes: " << clock() << "ms" << endl;
    return 0;
}
    • 1

    「POI2026 R1」Rozwiązanie pokojowe

    信息

    ID
    9642
    时间
    10000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 44ms
    4. Powered by Hydro v5.0.1 Community