题目链接

对每个三角形直接用行列进行标号，列号奇数为绿色，列号偶数为红色，判断相邻的三角形是否相邻然后进行 DFS。

样例已过，且调试结果显示走的路径是对的，但只有 $40$ 分，其他 RE 与 WA。求助！

测评记录

#include <iostream>

int n, ans;

bool ct[1000005][3], vis[1000005]; // ct 存储每个三角形与相邻的三角形是否连接, vis 为 dfs 时判重

int mp(int i, int j) // 将每个点从行列坐标映射到一维
{
    return (i - 1) * (i - 1) + j;
}

void dfs(int i, int j) // i, j 分别为横纵坐标
{
    if (vis[mp(i, j)]) // 判重
        return;
    vis[mp(i, j)] = true;
    ans++;
    // std::cout << i << " " << j << "\n";
    if (j % 2 == 1) // 绿色三角形
    {
        if (ct[mp(i, j)][0])
            dfs(i, j + 1);
        if (ct[mp(i, j)][1])
            dfs(i + 1, j + 1);
        if (ct[mp(i, j)][2])
            dfs(i, j - 1);
    }
    else // 红色三角形
    {
        if (ct[mp(i, j)][0])
            dfs(i, j - 1);
        if (ct[mp(i, j)][1])
            dfs(i - 1, j - 1);
        if (ct[mp(i, j)][2])
            dfs(i, j + 1);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < 2 * i; j += 2)
        {
            int x;
            std::cin >> x;
            ct[mp(i, j)][0] = ct[mp(i, j + 1)][0] = x & 1;     // 绿色三角与右边相连, 红色三角与左边相连
            ct[mp(i, j)][1] = ct[mp(i + 1, j + 1)][1] = x & 2; // 绿色三角与下面相连, 红色三角与上面相连
            ct[mp(i, j)][2] = ct[mp(i, j - 1)][2] = x & 4;     // 绿色三角与左边相连, 红色三角与右边相连
        }

    dfs(1, 1);

    std::cout << ans << "\n";

    return 0;
}

个人已做的一些尝试：

• 在 DFS 每拓展一步时判断边界，没有任何用处。
• 用邻接表存相连关系，已 AC。但是我还是想看看这个做法哪里有问题，求助！

邻接表测评信息

邻接表代码：

#include <iostream>
#include <utility>
#include <vector>

int ans = 1;
std::vector<std::pair<int, int>> mp[1005][2005];
bool vis[1005][2005];

void dfs(int i, int j)
{
    // std::cout << i << " " << j << std::endl;
    for (auto it : mp[i][j])
    {
        if (!vis[it.first][it.second])
        {
            vis[it.first][it.second] = true;
            ans++;
            dfs(it.first, it.second);
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n;

    std::cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < 2 * i; j += 2)
        {
            int x;
            std::cin >> x;
            if (x & 1)
            {
                mp[i][j].push_back({i, j + 1});
                mp[i][j + 1].push_back({i, j});
            }
            if (x & 2)
            {
                mp[i][j].push_back({i + 1, j + 1});
                mp[i + 1][j + 1].push_back({i, j});
            }
            if (x & 4)
            {
                mp[i][j].push_back({i, j - 1});
                mp[i][j - 1].push_back({i, j});
            }
        }

    vis[1][1] = true;
    dfs(1, 1);

    std::cout << ans << "\n";

    return 0;
}