hiho一下第71周《Constellations》题目分析

2
0

题意分析

小Hi最近爱上了星座,所以他买了一份星座图。今天晚上小明拿着星座图,对着夜空正在比较,他想知道现在夜空里能够看到哪些星座。小Hi所处的位置是正对北方,星座图也是正对北方绘制,所以在搜索星座的时候不需要旋转星座图。

算法分析

本题主要的考察点为二维字符串的匹配以及对于题目特殊条件的处理,和上一次比赛的《Lost in City》基本是相同的类型。

一个简单的做法是直接进行将每一幅星图 p_i 与星空图 s 进行模版匹配。

for i = 1 .. K
    exist[i] = false       // 假设星图p_i不在星空图s上
    for sx = 1 .. N
        for sy = 1 .. M    // 枚举星空图s的坐标作为匹配的左上角
            flag = true    // 假设匹配是成功的
            for px = 1 .. H
                for py = 1 .. W
                    if (p_i[px][py] == '#' && p_i[px][py] != s[sx + px - 1][sy + py - 1])
                        flag = false    // 星图p_i的位置有星星,而星空图s没有
                    end if
                end for
            end for
            if (flag) exist[i] = true;
        end for
    end for
end for

该算法的时间复杂度为 O(KMNHW)

对于给定的数据范围:1≤K≤20, 1≤M,N≤1000, 1≤W,H≤100。在极限数据下显然会超过时间限制,因此我们需要对算法进行优化。

在题目中,有一个我们没有用上的条件:每个星图 p_i 中包含的星星数量不超过20,整个星空图 s 的星星数量不超过5000

要查询一个星图 p_i 是否存在,只需要知道这个星图 p_i 上有星星的位置在星空图 s 上是否也有。而对于星图 p_i 上空白的区域我们并不关心。

也即是说,对于一个星图 p_i 我们实际关心的位置只有20个,也只需要关心这20个位置。

因此我们不妨将这20个星星的位置与左上角的相对坐标记录下来,进行匹配时只对这20个位置进行匹配:

for i = 1 .. K
    cnt = 0
    for px = 1 .. N
        for py = 1 .. M    
            if (p_i[px][py] == '#')            // 记录星图p_i中的每一颗星星
                cnt = cnt + 1
                offset[i][ cnt ].x = px - 1    // x轴偏差量
                offset[i][ cnt ].y = py - 1    // y轴偏差量
            end if 
        end for
    end for
end for 

for i = 1 .. K
    exist[i] = false       // 假设星图p_i不在星空图s上
    for sx = 1 .. N
        for sy = 1 .. M    // 枚举星空图s的坐标作为匹配的左上角
            flag = true    // 假设匹配是成功的
            for j = 1 .. the number of stars
                // offset[i][j] = {x, y} 表示第i个星图第j颗星星相对于左上角的偏移量
                if (s[ sx + offset[i][j].x ][ sy + offset[i][j].y ] != '#')
                    flag = false    // 星图p_i的位置有星星,而星空图s没有
                end if
            end for
            if (flag) exist[i] = true;
        end for
    end for
end for

offset数组需要进行预处理,花费的时间为 O(KHW),匹配的算法时间复杂度为 O(KMN)

由于星图十分稀疏,大部分星图 p_i 在进行第一个星星匹配时就会失败,因此该算法能够通过全部的测试点。

  • "而对于星图 p_i 上空白的区域我们并不关心",那么,对于一个匹配,如果在星图上市空白的,那么在sky上有可能不是空白的?

  • 我编写的时候就是按照如果星图上是空白的情况下,sky上不是空白时,我判定为false,得到的结果是Wrong Answer 40/100,所以题目这点没有讲清!去掉那个判断后,就直接 A了

  • 第一个算法不单是超时,还是个错误的算法。

  • 添加评论
  • reply

2 answer(s)

2

看上去这篇题解少分析了一种情况。

1

这OJ出毛病了吧,我这这么简明的代码居然还WA?不能理解

#include <vector>
#include <string>
#include <iostream>
using namespace std;

bool isMatch(const vector<pair<int, int>>& stars, const vector<string>& sky)
{
    for(int i = 0; i < sky.size(); i++)
        for(int j = 0; j < sky[0].size(); j++)
        {
            bool flag = true;
            for(int k = 0; k < stars.size(); k++)
            {
                int x = i+stars[k].first;
                int y = j+stars[k].second;
                if(x < 0 || y < 0 || x >= sky.size() || y >= sky[0].size() || sky[x][y] != '#')
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                return true;    
    }
    return false;
}


int main()
{
    vector<vector<pair<int,int>>>stars;
    int n;
    cin >> n;
    int first, second;
    for(int i = 0; i < n; i++)
    {
        cin >> first >> second;
        vector<pair<int,int>>tmp;
        for(int j = 0; j < first; j++)
        {
            string s;
            cin >>s;
            for(int k = 0; k < second; k++)
            {
                if(s[k] == '#')
                    tmp.push_back(make_pair(j,k));
            }
        }
        stars.push_back(std::move(tmp));
    }
    vector<string>sky;
    cin >> first >> second;
    sky.resize(first);
    for(int i = 0; i < first; i++)
        cin >> sky[i];
    for(int i = 0; i < n; i++)
    {
        if(isMatch(stars[i], sky))
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}
  • 还需要考虑星图的部分溢出了星空,但是溢出部分不包含星星的情况

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享