#include <iostream>
#include <queue>
#include <cctype>
#include <map>
struct Coor
{
int x; int y; int t;
Coor(int in_x, int in_y, int in_t) :
x(in_x), y(in_y), t(in_t)
{}
Coor() :
x(0), y(0), t(0)
{}
bool operator==(const Coor& another) const { return x == another.x && y == another.y; }
Coor& operator=(const Coor& another) { x = another.x; y = another.y; return *this; }
};
int N, M;
char mapArr[301][301];
bool boolArr[301][301];
std::queue<Coor> coorQueue;
std::map<char, std::pair<Coor, Coor>> specialMap; //装置对
int run()
{
while (mapArr[coorQueue.front().x][coorQueue.front().y] != '=')
{
boolArr[coorQueue.front().x][coorQueue.front().y] = true;
if (isalpha(mapArr[coorQueue.front().x][coorQueue.front().y]))
{
const std::pair<Coor, Coor>& curPair = specialMap[mapArr[coorQueue.front().x][coorQueue.front().y]];
if (curPair.first == coorQueue.front())
{
coorQueue.front() = curPair.second;
}
else
{
coorQueue.front() = curPair.first;
}
}
int nextX = coorQueue.front().x + 1, nextY = coorQueue.front().y;
if (mapArr[nextX][nextY] != '#' && !boolArr[nextX][nextY])
{
coorQueue.push(Coor(nextX, nextY, coorQueue.front().t + 1));
}
nextX = coorQueue.front().x - 1, nextY = coorQueue.front().y;
if (mapArr[nextX][nextY] != '#' && !boolArr[nextX][nextY])
{
coorQueue.push(Coor(nextX, nextY, coorQueue.front().t + 1));
}
nextX = coorQueue.front().x, nextY = coorQueue.front().y + 1;
if (mapArr[nextX][nextY] != '#' && !boolArr[nextX][nextY])
{
coorQueue.push(Coor(nextX, nextY, coorQueue.front().t + 1));
}
nextX = coorQueue.front().x, nextY = coorQueue.front().y - 1;
if (mapArr[nextX][nextY] != '#' && !boolArr[nextX][nextY])
{
coorQueue.push(Coor(nextX, nextY, coorQueue.front().t + 1));
}
coorQueue.pop();
}
return coorQueue.front().t;
}
int main()
{
std::cin >> N >> M;
for (int _i = 0; _i < N; ++_i)
{
for (int _j = 0; _j < M; ++_j)
{
std::cin >> mapArr[_i][_j];
if (isalpha(mapArr[_i][_j]))
{
std::pair<Coor, Coor>& curPair = specialMap[mapArr[_i][_j]];
if (curPair.first.x)
{
curPair.second.x = _i; curPair.second.y = _j;
}
else
{
curPair.first.x = _i; curPair.first.y = _j;
}
}
else if (mapArr[_i][_j] == '@')
{
coorQueue.push(Coor(_i, _j, 0));
}
}
}
//删除不成对的装置,将其置为#
for (std::map<char, std::pair<Coor, Coor>>::iterator it = specialMap.begin(); it != specialMap.end(); ++it)
{
if (!it->second.second.x)
{
mapArr[it->second.first.x][it->second.first.y] = '#';
it = specialMap.erase(it);
}
}
std::cout << run();
}
提交结果 3 6 13 15 16都tle了。
顺便问下,为何我一个测试点都下载不了呀?