#include <cstdio>
#include <cstring>

using namespace std;

long long int gcd(long long int a, long long int b)
{
	return (a == 0 || b == 0) ? (a + b) : (a >= b ? gcd(a % b, b) : gcd(a, b % a));
}

long long int lcm(long long int a, long long int b)
{
	return static_cast<long long int>(a) * static_cast<long long int>(b) / static_cast<long long int>(gcd(a, b));
}

bool solve(long long int base1, long long int step1, long long int base2, long long int step2, long long int max)
{
	long long int i, t;
	t = lcm(step1, step2);
	if(base1 >= base2)
	{
		for(i = max - (max - base1) % step1; i > max - t && i >= base1 && i >= base2; i -= step1)
		{
			if((i - base2) % step2 == 0)
			{
				return true;
			}
		}
	}
	else
	{
		for(i = max - (max - base2) % step2; i > max - t && i >= base1 && i >= base2; i -= step2)
		{
			if((i - base1) % step1 == 0)
			{
				return true;
			}
		}
	}
	return false;
}

int main(void)
{
	bool flag, map[2][100];
	int i, j, k, l, t, n, f, e, a, b, x[100], y[100], head[2], tail[2], queue[2][100];
	scanf("%d", &n);
	for(i = 0; i < n; i++)
	{
		memset(map, 0, sizeof(map));
		scanf("%d%d%d%d", &f, &e, &a, &b);
		for(j = 0; j < e; j++)
		{
			scanf("%d%d", &x[j], &y[j]);
		}
		head[0] = head[1] = tail[0] = tail[1] = 0;
		for(j = 0; j < e; j++)
		{
			if(a >= y[j] && (a - y[j]) % x[j] == 0)
			{
				queue[0][head[0]++] = j;
				map[0][j] = true;
			}
			if(b >= y[j] && (b - y[j]) % x[j] == 0)
			{
				queue[1][head[1]++] = j;
				map[1][j] = true;
			}
		}
		do
		{
			flag = false;
			for(j = 0; j < e; j++)
			{
				if(map[0][j] && map[1][j])
				{
					flag = true;
					break;
				}
			}
			if(flag)
			{
				break;
			}
			else
			{
				j = queue[0][tail[0]++];
				for(k = 0; k < e; k++)
				{
					if(!map[0][k] && solve(y[j], x[j], y[k], x[k], f - 1))
					{
						queue[0][head[0]++] = k;
						map[0][k] = true;
						flag = true;
					}
				}
				j = queue[1][tail[1]++];
				for(k = 0; k < e; k++)
				{
					if(!map[1][k] && solve(y[j], x[j], y[k], x[k], f - 1))
					{
						queue[1][head[1]++] = k;
						map[1][k] = true;
						flag = true;
					}
				}
			}
		}
		while(flag && head[0] >= tail[0] && head[1] >= tail[1]);
		if(flag)
		{
			printf("It is possible to move the furniture.\n");
		}
		else
		{
			printf("The furniture cannot be moved.\n");
		}
	}
	return 0;
}

• Just an easy bidirectional BFS (0) yaohua2000 2003-10-31 22:01:48