社区讨论
46分求助,其它都是WA
P1825[USACO11OPEN] Corn Maze S参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lode6f3h
- 此快照首次捕获于
- 2023/10/31 05:08 2 年前
- 此快照最后确认于
- 2023/11/06 20:29 2 年前
CPP
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <cctype>
using namespace std;
struct Point
{
int x, y;
bool operator<(const Point & b) const {return tie(x, y) < tie(b.x, b.y);}
};
struct Hash
{
size_t operator()(Point a)
{return a.x * 300 + a.y;}
};
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};
char Matrix[301][301];
int Arrive[301][301];
map<Point, Point> transit;
map<char, Point> tmp;
queue<Point> Q;
bool used[256];
int main()
{
fill(&Arrive[0][0], &Arrive[300][300], -1);
int N, M;
Point start;
cin >> N >> M;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= M; j++)
{
cin >> Matrix[i][j];
if (Matrix[i][j] == '@')
start = {i,j};
else if (isalpha(Matrix[i][j]))
{
auto p = tmp.find(Matrix[i][j]);
if (p != tmp.end())
{
transit.insert({tmp[Matrix[i][j]], {i, j}});
transit.insert({{i, j}, {tmp[Matrix[i][j]]}});
}
else
tmp.insert({Matrix[i][j], {i, j}});
}
}
}
Q.push(start), Arrive[start.x][start.y] = 0;
while (!Q.empty())
{
Point A = Q.front();
Q.pop();
char c = Matrix[A.x][A.y];
if (c == '=')
{
cout << Arrive[A.x][A.y];
return 0;
}
else if (isalpha(c) && !used[c])
{
Point B = transit[A];
if (Arrive[B.x][B.y] == -1)
{
used[c] = true;;
Arrive[B.x][B.y] = Arrive[A.x][A.y];
Q.push(B);
}
}
else
{
for (int i = 0; i < 4; i++)
{
int x = A.x + dx[i], y = A.y + dy[i];
if (x >= 1 && x <= N && y >= 1 && y <= M && Matrix[x][y] != '#' && Arrive[x][y] == -1)
{
Arrive[x][y] = Arrive[A.x][A.y] + 1;
Q.push({x, y});
}
}
}
}
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...