#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 510;
int T, n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];
void solve()
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[0][0] = 0;
deque<PII> deq;
deq.push_back({0, 0});
char state[] = {"\\/\\/"};
int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -1, 1};
int ix[] = {0, 0, -1, -1}, iy[] = {0, -1, -1, 0};
while (deq.size())
{
PII t = deq.front();
deq.pop_front();
if (st[t.x][t.y]) continue;
if (t.x == n && t.y == m) break;
st[t.x][t.y] = true;
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a > n || b < 0 || b > m) continue;
int w = g[t.x + ix[i]][t.y + iy[i]] != state[i];
int d = w + dist[t.x][t.y];
if (d < dist[a][b])
{
dist[a][b] = d;
if (w) deq.push_back({a, b});
else deq.push_front({a, b});
}
}
}
cout << dist[n][m] << endl;
}
int main()
{
cin >> T;
while (T -- )
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> g[i];
if ((n + m) & 1) puts("NO SOLUTION");
else solve();
}
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int INF = 0x3f3f3f3f;
int n, m, q;
int C, S, E;
int h[1010], e[20010], w[20010], ne[20010], idx;
int p[1010];
int dist[1010][110];
bool st[1010][110];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
dist[S][0] = 0;
heap.push({0, {S, 0}});
while (heap.size())
{
auto t = heap.top(); heap.pop();
int cost = t.x, ver = t.y.x, fuel = t.y.y;
if (st[ver][fuel]) continue;
st[ver][fuel] = true;
if (ver == E) return cost;
if (fuel < C && dist[ver][fuel + 1] > cost + p[ver])
{
dist[ver][fuel + 1] = cost + p[ver];
heap.push({cost + p[ver], {ver, fuel + 1}});
}
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i], d = w[i];
if (fuel >= d && dist[j][fuel - d] > cost)
{
dist[j][fuel - d] = cost;
heap.push({cost, {j, fuel - d}});
}
}
}
return -1;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> p[i];
for (int i = 0; i < m; i ++ )
{
int u, v, d;
cin >> u >> v >> d;
add(u, v, d), add(v, u, d);
}
cin >> q;
while (q -- )
{
cin >> C >> S >> E;
int t = dijkstra();
if (~t) cout << t << endl;
else puts("impossible");
}
return 0;
}
噩梦
题目描述
给定一张
N×M
的地图，地图中有
1
个男孩，
1
个女孩和
2
个鬼。
字符 . 表示道路，字符 X 表示墙，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 810;
int n, m;
char g[N][N];
int st[N][N];
PII boy, girl, ghost[2];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool check(int a, int b, int t)
{
if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 'X') return false;
for (int i = 0; i < 2; i ++ )
if (abs(ghost[i].x - a) + abs(ghost[i].y - b) <= 2 * t)
return false;
return true;
}
int solve()
{
memset(st, 0, sizeof st);
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> g[i];
int cnt = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == 'M') boy = {i, j};
else if (g[i][j] == 'G') girl = {i, j};
else if (g[i][j] == 'Z') ghost[cnt ++ ] = {i, j};
queue<PII> qb, qg;
qb.push(boy);
qg.push(girl);
int step = 0;
while (qb.size() || qg.size())
{
step ++ ;
for (int i = 0; i < 3; i ++ )
{
for (int j = 0, siz = qb.size(); j < siz; j ++ )
{
PII t = qb.front(); qb.pop();
int x = t.x, y = t.y;
if (!check(x, y, step)) continue;
for (int k = 0; k < 4; k ++ )
{
int a = x + dx[k], b = y + dy[k];
if (check(a, b, step))
{
if (st[a][b] == 2) return step;
if (!st[a][b])
{
st[a][b] = 1;
qb.push({a, b});
}
}
}
}
}
for (int i = 0; i < 1; i ++ )
{
for (int j = 0, siz = qg.size(); j < siz; j ++ )
{
PII t = qg.front(); qg.pop();
int x = t.x, y = t.y;
if (!check(x, y, step)) continue;
for (int k = 0; k < 4; k ++ )
{
int a = x + dx[k], b = y + dy[k];
if (check(a, b, step))
{
if (st[a][b] == 1) return step;
if (!st[a][b])
{
st[a][b] = 2;
qg.push({a, b});
}
}
}
}
}
}
return -1;
}
int main()
{
int T;
cin >> T;
while (T -- ) cout << solve() << endl;
return 0;
}
