Luogu P2445 [SDOI2005]动物园

本文主要是介绍Luogu P2445 [SDOI2005]动物园，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

全网好像就洛谷COGS还有几个不知名的网站有这个题
边做边玩做了一天最近效率极其低下

给下我的思路
从每个给出的信息开始搜
给出的信息包含了某个动物在时间后到达的位置
注意动物们可以停住不动
所以不一定是一定在准确的时间到达
只要最近能走到就可以
那么从给出的这个点开始搜
记一个数组叫表示这个笼子号动物在给定的信息中可以到达的次数
因为可能有多个信息包含这个动物
所以这个动物所在的笼子必须符合全部这些条件
也就是这个笼子被经过的次数要等于包含这个动物的信息的次数
这个笼子才能被这个动物到达
这样就预处理出了每个动物可以到达的笼子
我用一个存了起来
最后每个动物去配每个笼子就好了
很神奇的一点是
对于每个动物倒着遍历每个笼子快的不是一点半点！

#include <bits/stdc++.h>
#define

using namespace std;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
struct Cage {int x, y, w; set<int> v;}c[A];
struct Info {int t, x, y, id;}e[A], ans[A];
int n, p, v[A], info, now[A][A], ct[A]; char m[A][A];
bool vis[A][A], has[A][A], home[A], ok;
struct BFS {int x, y, st;};
void bfs(int x, int y, int totst, int anim) {
  queue<BFS> q; vis[x][y] = 1; q.push(BFS{x, y, totst});
  while (!q.empty()) {
    BFS fr = q.front(); q.pop(); int xx = fr.x, yy = fr.y, st = fr.st;
    if (st < 0) return;
    if (has[xx][yy] and st >= 0)
      for (int i = 1; i <= p; i++) {
        if (c[i].x == xx and c[i].y == yy) now[i][anim]++; else continue;
        if (now[i][anim] == ct[anim]) c[i].v.insert(anim);
      }
    for (int i = 0; i < 4; i++) {
      int fx = xx + dx[i], fy = yy + dy[i];
      if (fx < 1 or fx > n or fy < 1 or fy > n or vis[fx][fy] or m[fx][fy] == '*') continue;
      vis[fx][fy] = 1; q.push(BFS{fx, fy, st - 1});
    }
  }
}
void find(int fr) {
  if (fr > p and !ok) {
    ok = 1;
    for (int i = 1; i <= p; i++) printf("%d %d %d\n", i, ans[i].x, ans[i].y);
    exit(0);
  }
  for (int i = p; i >= 1; i--)
    if (c[i].v.count(fr) and !home[i]) {
      home[i] = 1; ans[fr] = Info{0, c[i].x, c[i].y, 0};
      find(fr + 1); home[i] = 0;
    }
}

int main(int argc, char const *argv[]) {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      scanf(" %c", &m[i][j]);
  scanf("%d", &p);
  for (int i = 1; i <= p; i++) scanf("%d%d", &c[i].x, &c[i].y), has[c[i].x][c[i].y] = 1;
  for (int i = 1; i <= p; i++) scanf("%d", &v[i]);
  scanf("%d", &info);
  for (int i = 1; i <= info; i++) scanf("%d%d%d%d", &e[i].t, &e[i].x, &e[i].y, &e[i].id), ++ct[e[i].id];
  for (int i = 1; i <= info; i++) {
    bfs(e[i].x, e[i].y, e[i].t * v[e[i].id], e[i].id);
    memset(vis, 0, sizeof vis);
  }
  find(1); return 0;
}
#include <bits/stdc++.h>
#define

using namespace std;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
struct Cage {int x, y, w; set<int> v;}c[A];
struct Info {int t, x, y, id;}e[A], ans[A];
int n, p, v[A], info, now[A][A], ct[A]; char m[A][A];
bool vis[A][A], has[A][A], home[A], ok;
struct BFS {int x, y, st;};
void bfs(int x, int y, int totst, int anim) {
  queue<BFS> q; vis[x][y] = 1; q.push(BFS{x, y, totst});
  while (!q.empty()) {
    BFS fr = q.front(); q.pop(); int xx = fr.x, yy = fr.y, st = fr.st;
    if (st < 0) return;
    if (has[xx][yy] and st >= 0)
      for (int i = 1; i <= p; i++) {
        if (c[i].x == xx and c[i].y == yy) now[i][anim]++; else continue;
        if (now[i][anim] == ct[anim]) c[i].v.insert(anim);
      }
    for (int i = 0; i < 4; i++) {
      int fx = xx + dx[i], fy = yy + dy[i];
      if (fx < 1 or fx > n or fy < 1 or fy > n or vis[fx][fy] or m[fx][fy] == '*') continue;
      vis[fx][fy] = 1; q.push(BFS{fx, fy, st - 1});
    }
  }
}
void find(int fr) {
  if (fr > p and !ok) {
    ok = 1;
    for (int i = 1; i <= p; i++) printf("%d %d %d\n", i, ans[i].x, ans[i].y);
    exit(0);
  }
  for (int i = p; i >= 1; i--)
    if (c[i].v.count(fr) and !home[i]) {
      home[i] = 1; ans[fr] = Info{0, c[i].x, c[i].y, 0};
      find(fr + 1); home[i] = 0;
    }
}

int main(int argc, char const *argv[]) {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      scanf(" %c", &m[i][j]);
  scanf("%d", &p);
  for (int i = 1; i <= p; i++) scanf("%d%d", &c[i].x, &c[i].y), has[c[i].x][c[i].y] = 1;
  for (int i = 1; i <= p; i++) scanf("%d", &v[i]);
  scanf("%d", &info);
  for (int i = 1; i <= info; i++) scanf("%d%d%d%d", &e[i].t, &e[i].x, &e[i].y, &e[i].id), ++ct[e[i].id];
  for (int i = 1; i <= info; i++) {
    bfs(e[i].x, e[i].y, e[i].t * v[e[i].id], e[i].id);
    memset(vis, 0, sizeof vis);
  }
  find(1); return 0;

 

这篇关于Luogu P2445 [SDOI2005]动物园的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！