牛客网湘潭大学程序设计竞赛F题:maze
程序员文章站
2022-05-24 09:38:24
...
emmmmmmmmmmmmmm因为要写离散作业就没空好好做题,选了两道题(其他不会)做了一下。
F题一个小搜索题,写博客觉得没必要,不写又觉得自己那么久都没做出来。。。。
题意是普通的宽搜加传送魔法阵,所以就应该用更新距离的方式入队列,而不是用vised数组记录。
#include <bits/stdc++.h>
using namespace std;
#define N 301
typedef pair<int, int> P;
#define f first
#define s second
#define INF 0x3f3f3f3f
//bool vis[N * N];
queue<P> que;
char maze[N][N];
int d[N * N];
int n, m, q;
map<P, P> mp;
P tmp1, tmp2;
int sx, sy, tx, ty;
int dx[] = {0, 0, 1, -1, 0};
int dy[] = {1, -1, 0, 0, 0};
int dfs()
{
// memset(vis, 0, sizeof(vis));
while(!que.empty()) que.pop();
memset(d, 0x3f, sizeof(d));
d[sx * m + sy] = 0;
// vis[sx * (n - 1) + sy] = true;
que.push(P(sx, sy));
P tmp;
int x, y;
while(!que.empty()){
P h = que.front();que.pop();
x = h.f, y = h.s;
//printf("%d %d\n", x, y);
if(x == tx && y == ty)
continue;
// return d[x * m + y];
for(int i = 0; i < 5; i++){
int xx = x + dx[i], yy = y + dy[i];
if(maze[xx][yy] == '#' || xx >= n || yy >= m || xx < 0 || yy < 0) continue;
if(d[x * m + y] + 1 < d[xx * m + yy]){
d[xx * m + yy] = d[x * m + y] + 1;
que.push(P(xx, yy));
}
}
tmp.f = x;
tmp.s = y;
if(mp.count(tmp) == 1){
tmp1 = mp[tmp];
if(maze[tmp1.f][tmp1.s] != '#' && d[tmp1.f * m + tmp1.s] > d[x * m + y] + 3){
d[tmp1.f * m + tmp1.s] = d[x * m + y] + 3;
que.push(tmp1);
}
}
}
if(d[tx * m + ty] < INF) return d[tx * m + ty];
return -1;
}
int main()
{
// freopen("date.txt", "r", stdin);
while(scanf("%d%d%d", &n, &m, &q) != EOF){
for(int i = 0; i < n; i++){
scanf("%s", maze[i]);
}
mp.clear();
for(int i = 0; i < q; i++){
scanf("%d%d%d%d", &tmp1.f, &tmp1.s, &tmp2.f, &tmp2.s);
mp[tmp1] = tmp2;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(maze[i][j] == 'S'){
sx = i;sy = j;
}
else if(maze[i][j] == 'T'){
tx = i;ty = j;
}
}
}
//printf("%d\n", mp.count(P(1, 2)));
printf("%d\n", dfs());
}
return 0;
}
上一篇: Struts2报错:HTTP Status 404 - No result defined for action and result input
下一篇: UVA10603 FILL(宽搜)
推荐阅读