之前RXZ说做了一道题没感觉就没必要写笔记，所以一直没写，但是今天遇到了一道题。非常有意思，是一种我不知道的做法。

洛谷 P1141 01迷宫

由于放链接会发生一些不妙的事情，请自行去洛谷查看。

题意没有任何的弯弯绕绕。

看到题的tag是广搜就先写了个bfs，然后Tle了3个点。

bfs tle代码

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>

using namespace std;

const int MAXN = 1e3 + 5;
const int dx[] = {-1, +1, 0, 0};
const int dy[] = {0, 0, +1, -1};

int n, m, ans;
bool visit[MAXN][MAXN], map[MAXN][MAXN];

void input()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%1d", &map[i][j]);
}

int get(int i, int j)
{
    memset(visit, 0, sizeof(visit));
    queue<pair<int, int>> q;
    int ans = 0;

    q.push({i, j});

    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second;
        q.pop();

        if (!visit[x][y])
        {
            visit[x][y] = true;
            ans++;
        }else
            continue;

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];

            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
                if (map[nx][ny] ^ map[x][y])
                    q.push({nx, ny});
        }
    }

    return ans;
}

void work()
{
    while (m--)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        printf("%d\n", get(x, y));
    }
}

int main()
{
    input();

    work();

    return 0;
}

非常的不妙，愉快的重写了个dfs自以为能省点时间（然而事实上只减少了0.01s的时间，可以看作误差）。

dfs tle代码

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>

using namespace std;

const int MAXN = 1e3 + 5;
const int dx[] = {-1, +1, 0, 0};
const int dy[] = {0, 0, +1, -1};

int n, m, ans;
bool visit[MAXN][MAXN], map[MAXN][MAXN];

void input()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%1d", &map[i][j]);
}

void dfs(int x, int y)
{
    if (!visit[x][y])
    {
        visit[x][y] = true;
        ans++;
    }
    else
        return;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];

        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
            if (map[nx][ny] ^ map[x][y])
                dfs(nx, ny);
    }
}

void work()
{
    while (m--)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        memset(visit, 0, sizeof(visit));
        ans = 0;
        dfs(x, y);
        printf("%d\n", ans);
    }
}

int main()
{
    input();

    work();

    return 0;
}

再想了10分钟还是没头绪，就无奈的打开了题解（~~说好的学术模式~~）。

自豪的说一句，我的代码的可读性比他们的高不少：

dfsAC代码！

#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 1e3 + 5;
const int dx[] = {-1, +1, 0, 0};
const int dy[] = {0, 0, +1, -1};

int n, m, used[MAXN][MAXN], ans[MAXN * MAXN + 5];
bool map[MAXN][MAXN];

void input()
{
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%1d", &map[i][j]);
}

void dfs(int x, int y, int count)
{
    if (used[x][y] != -1)
        return;

    used[x][y] = count;
    ans[count]++;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];

        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
            if (map[nx][ny] ^ map[x][y])
                dfs(nx, ny, count);
    }
}

void work()
{
    memset(used, -1, sizeof(used));

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        if (used[x][y] == -1)
            dfs(x, y, i);
        else
            ans[i] = ans[used[x][y]];
    }

    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
}

int main()
{
    input();

    work();

    return 0;
}

他们判断是否能走的方法真是让我哭笑不得：

void dfs(int r,int c,int z,int lll){
    if (r<0 || r>=n || c<0 || c>=n || f[r][c]!=-1 || s[r][c]-'0'!=z)return;
    f[r][c]=lll;ans[lll]++;
    dfs(r-1,c,!z,lll);dfs(r+1,c,!z,lll);dfs(r,c-1,!z,lll);dfs(r,c+1,!z,lll);
}