Little Green Onion Takes Candy

Problem#

Little Green Onion put the candies he bought into the refrigerator, but now he wants to eat the candies and hopes to take the candies he wants to eat out of the refrigerator. Specifically, in an $N$ by $N$ grid, there are several candies, each of which is placed either horizontally or vertically. For a horizontally placed candy, we can only move it left or right (any distance, but cannot cross other candies), while for a vertically placed candy, we can only move it up or down. Our goal is to move the candy numbered $1$ out of the refrigerator, and the way to move it out is to allow that candy to move to the right boundary of the grid (only the candy number one can be moved out, other candies cannot be moved out even if they are at the boundary). We guarantee that each candy has a length of at least $2$, and candy number $1$ is definitely placed horizontally. During the movement of the candy, it cannot cross other candies. The question is, under the above constraints, how many moves does Little Green Onion need to make at least to move candy number $1$ out of the refrigerator? If candy number $1$ is already on the right boundary, please output $0$.

For $100%$ of the data, $1\leq N\leq8$, with at most $13$ different candies, the answer does not exceed $10$ steps.

Solution#

Search! Search! Search!

Move any candy any number of steps each time, store each state (to check for duplicates), and then use BFS.

How to store? Actually, a candy only needs to record one coordinate position, the other remains unchanged.

For the coordinates of these candies, we can store them using an $n$-base number, with at most $13$ different candies, so $n^{13} - 1$ is enough; calculating, unsigned long long is sufficient.

Note#

Before inserting a new state, first check whether the state to be inserted is the answer; otherwise, it may be stuck on timeout (because this took 2 hours QAQ).

Code#

#include<bits/stdc++.h>
#define ull unsigned long long 
#define DOWN 1
#define RIGHT 0

using namespace std;

const int N = 10;
int a[N][N], n, typenum;
const int M = 15;
// map compress ull 
map<ull, int> step;
queue<ull> qwq;
int towards[M], pos[M], len[M], another_pos[M];

void trans(ull state)
{
	int cnt = typenum;
	while(cnt >= 1)
	{
		ull b = state % n;
		pos[cnt] = b;
		state /= n;
		if(towards[cnt] == DOWN)
		{
//			cout << cnt << " point DOWN" << endl;
			for(int i = b;i <= b + len[cnt] - 1;i++)
			{
				a[i][another_pos[cnt]] = cnt;
			}
		}
		else
		{
//			cout << cnt << " point RIGHT" << endl;
			for(int i = b;i <= b + len[cnt] - 1;i++)
			{
				a[another_pos[cnt]][i] = cnt;
			}
		}
		cnt --;
	}
}

ull pack()
{
	ull start = 0;
	for(int i = 1;i <= typenum;i++)
	{
		start = start * n + pos[i];
	}
	return start;
}

int main()
{
	freopen("take.in", "r", stdin);
        freopen("take.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			cin >> a[i][j];
		}
	}
	
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			if(a[i][j] == 0) continue;
			int cl = a[i][j];
			if(a[i + 1][j] == cl) towards[cl] = DOWN;
			else towards[cl] = RIGHT;
			
			if(towards[cl] == DOWN) pos[cl] = i, another_pos[cl] = j;
			else pos[cl] = j, another_pos[cl] = i;
			
			int x = i, y = j;
			len[cl] = 0;
			while(x <= n && y <= n && a[x][y] == cl)
			{
				a[x][y] = 0;
				(towards[cl] == DOWN) ? (x ++) : (y++) ;
				len[cl] ++; 
			}
			typenum = max(typenum, cl);
		}
	}
	ull start = 0;
	for(int i = 1;i <= typenum;i++)
	{
		start = start * n + pos[i];
	}
	step[start] = 0;
	qwq.push(start);
	
	while(qwq.size())
	{
		ull t = qwq.front();
		qwq.pop();
		memset(a, 0, sizeof a);
		trans(t);
		if(pos[1] + len[1] - 1 >= n)
		{
			cout << step[t] << endl;
			exit(0);
		}
		for(int i = 1;i <= typenum;i++)
		{
			if(towards[i] == DOWN)
			{
				for(int movement = 1;movement <= n;movement++)
				{
					if(a[pos[i] + len[i] - 1 + movement][another_pos[i]] != 0 || pos[i] + len[i] - 1 + movement > n) break;
					pos[i] = pos[i] + movement;
					ull now = pack();
					pos[i] -= movement;
					if(step[now] != 0)
						continue;
					qwq.push(now), step[now] = step[t] + 1;
					/*just here*/if(i == 1 && pos[i] + len[i] - 1 + movement == n)
					{
						cout << step[now];
						exit(0);
					}
				}
				
				for(int movement = -1;movement >= -n;movement--)
				{
					if(a[pos[i] + movement][another_pos[i]] != 0 || pos[i] + movement < 1) break;
					pos[i] = pos[i] + movement;
					ull now = pack();
					pos[i] -= movement;
					if(step[now] != 0)
						continue;
					qwq.push(now), step[now] = step[t] + 1;
					if(i == 1 && pos[i] + len[i] - 1 + movement == n)
					{
						cout << step[now];
						exit(0);
					}
				}
			}
			else
			{
				for(int movement = 1;movement <= n;movement++)
				{
					if(a[another_pos[i]][pos[i] + len[i] - 1 + movement] != 0 || pos[i] + len[i] - 1 + movement > n) break;
					pos[i] = pos[i] + movement;
					ull now = pack();
					pos[i] -= movement;
					if(step[now] != 0)
						continue;
					qwq.push(now), step[now] = step[t] + 1;
					if(i == 1 && pos[i] + len[i] - 1 + movement == n)
					{
						cout << step[now];
						exit(0);
					}
				}
				
				for(int movement = -1;movement >= -n;movement--)
				{
					if(a[another_pos[i]][pos[i] + movement] != 0 || pos[i] + movement < 1) break;
					pos[i] = pos[i] + movement;
					ull now = pack();
					pos[i] -= movement;
					if(step[now] != 0)
						continue;
					qwq.push(now), step[now] = step[t] + 1;
					if(i == 1 && pos[i] + len[i] - 1 + movement == n)
					{
						cout << step[now];
						exit(0);
					}
				}
			}
		}
		//step will be updated when expanding from this point 
	}
	
	return 0; 
}