Luogu P2445 [SDOI2005]动物园

动物园"/>

Luogu P2445 [SDOI2005]动物园

题目链接：传送门

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

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

#include <bits/stdc++.h>
#define A 101using 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;
}