leetcode1036(2022.1.11)

leetcode1036(2022.1.11)

string vectorToString(vector a)
{
	if (a[0] < 0 || a[0] > 999999)
	{
		return "";
	}
	if (a[1] < 0 || a[1] > 999999)
	{
		return "";
	}
	string ans;
	ans = to_string(a[0]) + '|' + to_string(a[1]);
	return ans;
}
bool isEscapePossible(vector>& blocked, vector& source, vector& target) {
	int len = blocked.size();
	int max = len * len;
	unordered_set con;
	unordered_set passPoint;
	for (auto tmp : blocked)
	{
		con.insert(vectorToString(tmp));
	}
	con.insert("");
	queue> q;
	q.push(source);
	passPoint.insert(vectorToString(source));
	//cout << max << endl;
	while (q.size() > 0)
	{
		//上下左右
		//如果队列里元素的个数>一个值，说明源点没有被围住，因为这些点能围成的最大面积是一定的
		//cout << endl;
		//cout << passPoint.size() <= max)
		{
			break;
		}
		vector tmp = q.front();
		tmp[0] = q.front()[0] + 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			//cout << "1:" << tmp[0] << "," << tmp[1] << " ";
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == target)
		{
			return true;
		}
		tmp[0] = q.front()[0] - 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			//cout<< "2:" << tmp[0] << "," << tmp[1] << " ";
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == target)
		{
			return true;
		}
		tmp[0] = q.front()[0];
		tmp[1] = q.front()[1] - 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			//cout<< "3:" << tmp[0] << "," << tmp[1] << " ";
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == target)
		{
			return true;
		}
		tmp[1] = q.front()[1] + 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			//cout<< "4:" << tmp[0] << "," << tmp[1] << " ";
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == target)
		{
			return true;
		}
		q.pop();
	}
	if (q.size() == 0)
	{
		return false;
	}
	q = queue>();
	passPoint.clear();
	q.push(target);
	passPoint.insert(vectorToString(target));
	while (q.size() > 0)
	{
		//上下左右
		//如果队列里元素的个数>一个值，说明源点没有被围住，因为这些点能围成的最大面积是一定的
		if (passPoint.size() >= max)
		{
			break;
		}
		vector tmp = q.front();
		tmp[0] = q.front()[0] + 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == source)
		{
			return true;
		}
		tmp[0] = q.front()[0] - 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == source)
		{
			return true;
		}
		tmp[0] = q.front()[0];
		tmp[1] = q.front()[1] - 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == source)
		{
			return true;
		}
		tmp[1] = q.front()[1] + 1;
		if ((!con.count(vectorToString(tmp))) && (!passPoint.count(vectorToString(tmp))))
		{
			q.push(tmp);
			passPoint.insert(vectorToString(tmp));
		}
		if (tmp == source)
		{
			return true;
		}
		q.pop();
	}
	if (q.size() == 0)
	{
		return false;
	}
	return true;
}

大体思想是：如果当前遍历的格子数量大于F(障碍数)，说明该点不会被障碍围住，只要起点和终点都不会被障碍围住就行了（没想到，转化问题能力还是太差了）
这个用1e5会tle，原因我觉得是因为我是用字符串哈希，如果用数字的话其实一步就可以了，第一维乘一个大于数组长的数+第二位即可，用longlong也不会溢出，这波属于是画蛇添足了
还有vector的erase貌似挺吃性能的。所以不要用vector代替queue！