AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 691. bfs + 哈希表    原题链接    简单

作者: 作者的头像   Sufferingcreatinglife ,  2022-06-23 23:04:01 ,  所有人可见 ,  阅读 37


2


代码:

#include <iostream>
#include <queue>
#include <unordered_map>

#define l first
#define r second

using namespace std;

typedef pair<int,int> PII;
const int N = 1010;
int a[N][N];
queue<PII> q;
int n,s;

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

    int res,idx,ans,id;
    cin >> n;
    int k = 0;

    while(n -- )
    {
        unordered_map<int,PII> mp;
        int b[1000010] = {0};
        idx = 1;
        res = 0;
        id = 0;
        cin >> s;
        for(int i = 0;i < s;i ++ )
            for(int j = 0;j < s;j ++ )
            {
                cin >> a[i][j];
                mp[a[i][j]] = {i,j};
            }

        while(idx <= s * s)
        {
            int start = idx;
            ans = 0;
            q.push(mp[idx]);

            while(!q.empty())
            {
                PII x = q.front();
                int dx = x.l,dy = x.r;
                q.pop();
                ans ++ ;
                b[a[dx][dy]] = 1;
                idx = max(idx,a[dx][dy]);
                //if(i == 1 && j == 1) cout << dx << " " << dy << endl;
                //cout << s << endl;

                if(dx + 1 < s && !b[a[dx + 1][dy]] && (a[dx + 1][dy] == a[dx][dy] + 1)) 
                    q.push({dx + 1,dy});
                if(dx - 1 >= 0 && !b[a[dx - 1][dy]] && (a[dx - 1][dy] == a[dx][dy] + 1)) 
                    q.push({dx - 1,dy});
                if(dy + 1 < s && !b[a[dx][dy + 1]] && (a[dx][dy + 1] == a[dx][dy] + 1)) 
                    q.push({dx,dy + 1});
                if(dy - 1 >= 0 && !b[a[dx][dy - 1]] && (a[dx][dy - 1] == a[dx][dy] + 1)) 
                    q.push({dx,dy - 1});
            }
            if(ans > res)
                {
                    res = ans;
                    id = start;
                }
            idx += 1;
        }

        printf("Case #%d: %d %d\n",++ k,id,res);
    }

    return 0;
}

0 评论

你确定删除吗?

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息