社区讨论

20求助

P114101迷宫参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo7z11pw
此快照首次捕获于
2023/10/27 10:05
2 年前
此快照最后确认于
2023/10/27 10:05
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;

typedef struct Point
{
    int i;
    int j;
}
point;

int m;
int n;
int i;
int j;
int maxans;
char a[1005][1005];
int visited[1005][1005];
int v[1005][1005];
int cnt;
queue <point> q;

inline void init()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        scanf("%s", a[i]);
	}
}

inline int check(int i, int j, int now)
{
    return i >= 0 && j >= 0 && i < n && j < n && a[i][j] != now && visited[i][j] == 0;
}

inline int check(int i, int j)
{
    return i >= 0 && j >= 0 && i < n && j < n && v[i][j] == 0;
}

void dfs(int i, int j)
{
    bool flag = 1;
    v[i][j] = 1;
    if (visited[i][j-1] > visited[i][j] && check(i, j - 1))
    {
        dfs(i, j - 1);
        flag = 0;
    }
    if (visited[i][j+1] > visited[i][j] && check(i, j + 1))
    {
        dfs(i, j + 1);
        flag = 0;
    }
    if (visited[i-1][j] > visited[i][j] && check(i - 1, j))
    {
        dfs(i - 1, j);
        flag = 0;
    }
    if (visited[i+1][j] > visited[i][j] && check(i + 1, j))
    {
        dfs(i + 1, j);
        flag = 0;
    }
    v[i][j] = 0;
    if (flag)
    {
        if (maxans < visited[i][j])
        {
            maxans = visited[i][j];
        }
        return;
    }
}

int main(int argc, char **argv)
{
    init();
    while (m--)
    {
        scanf("%d%d", &i, &j);
        i--;
        j--;
        if (visited[i][j] == 0)
        {
            cnt = 1;
            q.push({i, j});
            while (!q.empty())
            {
                point s = q.front();
                q.pop();
                visited[s.i][s.j] = cnt;
                int now = a[s.i][s.j];
                if (check(s.i + 1, s.j, now))
                {
                    q.push({s.i + 1, s.j});
                    visited[s.i+1][s.j] = cnt;
                    cnt++;
                }
                if (check(s.i - 1, s.j, now))
                {
                    q.push({s.i - 1, s.j});
                    visited[s.i-1][s.j] = cnt;
                    cnt++;
                }
                if (check(s.i, s.j + 1, now))
                {
                    q.push({s.i, s.j + 1});
                    visited[s.i][s.j+1] = cnt;
                    cnt++;
                }
                if (check(s.i, s.j - 1, now))
                {
                    q.push({s.i, s.j - 1});
                    visited[s.i][s.j-1] = cnt;
                    cnt++;
                }
            }
            printf("%d\n", cnt);
        }
        else
        {
            maxans = visited[i][j];
            dfs(i, j);
            printf("%d\n", maxans);
            maxans = 0;
        }
    }
	return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...