题解-AT_abc311_d

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

觉得自己的写法还算简洁，就来一篇。

题面大意

初始时，你处于静止状态，站在冰上，你可以选择一个方向，然后一直向这个方向移动直到碰到障碍物，然后重新变为静止状态，求你一共能走到多少点。

解题思路

这个可以应用 bfs 求解。

我们将状态定义为 $(x,y,pos)$，即坐标和方向。

然后这样设计状态写出来的程序就比较自然。

剩下其实就是 bfs 了，这里说一点注意事项。

1. 即使位置相同，能走到的点也不一定是相同的（方向不同），所以标记数组要开三维。
2. 相同位置只算一次贡献，可以开一个二维数组累计，二维数组和三维数组不要混用。
3. 注意判断两种情况的条件：即保持当前方向和向四周扩展，只有对应方向有障碍物的时候才能向四周扩展。

#include <stdio.h>
#include <queue>

#define maxn ;

int n, m, mp[maxn][maxn];
int dx[4] = {0, 1, 0, -1},
    dy[4] = {1, 0, -1, 0};

int vis[maxn][maxn][4], book[maxn][maxn], res;

std::queue<std::pair<std::pair<int, int>, int>> qu;

char ch;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            do
            {
                ch = getchar();
            } while (ch != '.' && ch != '#');
            mp[i][j] = (ch == '.');
        }

    qu.push({{2, 2}, 0});
    qu.push({{2, 2}, 1});
    qu.push({{2, 2}, 2});
    qu.push({{2, 2}, 3});
    while (!qu.empty())
    {
        auto u = qu.front();
        qu.pop();
        if (!mp[u.first.first][u.first.second] || u.first.first == 0 || u.first.second == 0 || u.first.first > n || u.first.second >= m)
            continue;
        if (vis[u.first.first][u.first.second][u.second])
            continue;
        vis[u.first.first][u.first.second][u.second] = 1;
        if (!book[u.first.first][u.first.second])
            book[u.first.first][u.first.second] = 1,
            res++;
        if (mp[u.first.first + dx[u.second]][u.first.second + dy[u.second]])
            qu.push({{u.first.first + dx[u.second], u.first.second + dy[u.second]}, u.second});
        else
            for (int i = 0; i < 4; i++)
                qu.push({{u.first.first + dx[i], u.first.second + dy[i]}, i});
    }

    printf("%d", res);

    return 0;
}