题意分析

本题要求根据给定的房子布局图（包含房间数量、猫和老鼠的初始房间以及猫门和老鼠门的连接情况），判断两个条件：一是是否存在猫和老鼠的行走路线使它们在某个房间相遇；二是老鼠是否能够经过至少两个房间后回到自己的“家”房间且过程中不遇到猫。猫只能走猫门，老鼠只能走老鼠门，且门是单向的。

解题思路

1. 数据读取与初始化：
   • 读取测试用例数量 T。
   • 对于每个测试用例，读取房间数量 n、猫的初始房间 cat 和老鼠的初始房间 mouse。
   • 初始化存储猫门连接关系的 road 数组（vector 形式），并读取猫门的连接信息，以 -1 -1 结束。
2. 猫的行走路径标记：
   • 调用 cat_walk 函数，该函数先调用 read_road 读取猫门信息并清空 road 数组（以防之前数据残留）。
   • 调用 cat_dfs 从猫的初始房间 cat 开始深度优先搜索，标记猫能到达的房间（danger 数组）。
3. 老鼠的行走路径判断：
   • 调用 mouse_walk 函数，同样先调用 read_road 读取老鼠门信息并清空 road 数组。
   • 调用 mouse_dfs 从老鼠的初始房间 mouse 开始深度优先搜索。
   • 在 mouse_dfs 中，如果到达的房间已被猫标记（danger[x] 为 true），则设置 meet 为 true 表示猫鼠会相遇；如果能到达老鼠的初始房间 mouse，则设置 can 为 true 表示老鼠能回到家。
4. 输出结果：
   • 根据 meet 和 can 的值，按照要求的格式输出结果。

复杂度分析

1. 时间复杂度：
   • 读取输入数据的时间复杂度取决于输入的边数，对于猫门和老鼠门的读取，假设猫门和老鼠门的数量分别为 e1 和 e2，则读取时间复杂度为 $O(e1 + e2)$。
   • 猫的深度优先搜索 cat_dfs 时间复杂度为 $O(e1)$，因为每个猫门最多被遍历一次。
   • 老鼠的深度优先搜索 mouse_dfs 时间复杂度为 $O(e2)$，同理每个老鼠门最多被遍历一次。
   • 总体时间复杂度为 $O(e1 + e2)$。
2. 空间复杂度：
   • 存储猫门和老鼠门连接关系的 road 数组（vector 形式），最坏情况下存储所有边的信息，空间复杂度为 $O(e1 + e2)$。
   • 标记猫能到达房间的 danger 数组和标记老鼠是否访问过房间的 visit 数组，大小为房间数量 n，空间复杂度为 $O(n)$。
   • 总体空间复杂度为 $O(e1 + e2 + n)$。

代码实现

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <cstdlib>

#define min(a,b) (((a) < (b)) ? (a) : (b))
#define max(a,b) (((a) > (b)) ? (a) : (b))
using namespace std;
const int MAX = 100;

int n;
int cat;
int mouse;
bool danger[MAX + 2];
vector<int> road[MAX + 2];

// 读取猫门或老鼠门的连接信息
void read_road()
{
    for (int i = 1; i <= MAX; i++)
        road[i].clear();
    int a, b;
    while (scanf("%d%d", &a, &b) && a != -1 && b != -1)
        road[a].push_back(b);
}

// 猫的深度优先搜索，标记猫能到达的房间
void cat_dfs(int x)
{
    danger[x] = true;

    int sz = road[x].size();
    for (int i = 0; i < sz; i++)
    {
        if (!danger[road[x][i]])
            cat_dfs(road[x][i]);
    }
}

// 猫的行走路径处理函数
void cat_walk()
{
    read_road();
    memset(danger, 0, sizeof(danger));
    cat_dfs(cat);
}

bool visit[MAX + 2];
bool meet;
bool can;

// 老鼠的深度优先搜索，判断是否与猫相遇以及能否回到家
void mouse_dfs(int x)
{
    if (danger[x])
    {
        meet = true;
        return;
    }

    visit[x] = true;
    int sz = road[x].size();
    for (int i = 0; i < sz; i++)
    {
        if (road[x][i] == mouse)
            can = true;
        if (!visit[road[x][i]])
            mouse_dfs(road[x][i]);
    }
}

// 老鼠的行走路径处理函数
void mouse_walk()
{
    read_road();
    meet = can = false;
    memset(visit, 0, sizeof(visit));
    mouse_dfs(mouse);
}

int main()
{
    int T;
    int kase = 0;
    scanf("%d", &T);
    while (++kase <= T)
    {
        scanf("%d%d%d", &n, &cat, &mouse);
        cat_walk();
        mouse_walk();
        printf("%c %c\n", (meet)? 'Y' : 'N', (can)? 'Y' : 'N');
    }
    return 0;
}