(竞赛题)计算没有被象攻击的方格数量

问题描述 投票:0回答:2

我的解决方案在下面。

国际象棋中的象是攻击同一条对角线上(两条对角线上)的所有方格的棋子。

Picture

Shakhriyar 将 m 个主教放在大小为 n * n 的棋盘上。现在他想数一下没有被主教攻击的方格有多少个。在这件事上帮助 Shahriyar。

输入数据 第一行包含两个整数:棋盘的大小 n (1 ≤ n ≤ 10^6) 和象的数量 m (1 ≤ m ≤ 10^5)。接下来的 m 行中的每一行都包含一对整数: r[i] и c[i] (1 ≤ r[i], c[i] ≤ n) - 主教编号 i 所在的行数和列数。主教编号从 1 到 m。所有主教都位于不同的广场上。

输出数据 打印未被主教攻击的方格数。

https://www.eolymp.com/en/problems/9630

输入示例#1

10 6

4 7

8 5

8 7

6 2

9 7

8 4

输出示例#1

33

我到这里就解决了:

(抱歉图片有点乱)

Picture 1Picture 2

对角线=2n-1

d-对角线数

(i;j)-点(y,x)的坐标

来自图1:

1:(6;1)

2:(5;1); (6;2)

3:(4;1); (5;2); (6;3)

4:(3;1); (4;2); (5;3); (6;4)

...

10:(1;5); (2;6)

11:(1;6)

d=n-(i-j);

来自图2:

1:(1;1)

2:(1;2); (2;1)

3:(1;3); (3;1); (2;2)

4:(1;4) (4;1) (2;3) (3;2)

...

d=i+j-1;

对角线交点:

图1(2)中的对角线 图2(1)中的对角线
1, 11 6
2, 10 5,6,7
3, 9 4,5,6,7,8
4、8 3,4,5,6,7,8,9
5、7 2,3,4,5,6,7,8,9,10
6 1,2,3,4,5,6,7,8,9,10,11

在求点数时,交叉点阻碍了我。我该如何解决这个问题?

我的代码(C++):

#include<iostream>
#include<set>
using namespace std;
int main(){
    set<int> hit_diagonals1,hit_diagonals2;
    int n,m;
    cin>>n>>m;
    for(int k=0,i,j; k<m; k++){///O(m)-->1e5
        cin>>i>>j;
        hit_diagonals1.insert(n-(i-j));
        hit_diagonals2.insert(i+j-1);
    }
    int cnt=0;//hit_points_number
    
    //.....
    
    cout<<n*n-cnt<<'\n';
    return 0;
}

c++ algorithm c++17 chess
2个回答
3
投票

您可以使用对角线扫描线算法在 O(m log m) 时间内解决此问题。

首先,我们将 x+y 恒定的对角线称为“反斜杠对角线”,而“斜杠”对角线将是 x-y 恒定的对角线。

现在我们可以按从 0 到 2m+1(最大 x+y)的顺序考虑反斜杠对角线。

首先,列出“事件”。 对于每个主教位置 (x,y),记录:

  • (x+y, 'cover'): 表示主教完全覆盖的反斜杠对角线;
  • (abs(x-y), 'enter'):主教开始覆盖其斜线对角线的第一个反斜线对角线:
  • (m+m-1-abs(x,y), ' exit'):第一个反斜杠对角线,主教不再覆盖其斜杠对角线。

制作一个最初为空的字典

slashes
来跟踪覆盖每个斜线对角线的主教数量。 在修改此映射时,您还将确保可以跟踪非零条目的数量。

现在,按反斜杠对角线对事件进行排序,并按顺序处理它们,按反斜杠对角线分组。

对于每个反斜杠组 <= (m-1)+(m-1):

  • 累计自上次发生事件的反斜杠组以来未受攻击的方块数量。 由于这些反斜杠中没有事件,这意味着您可以使用简单的公式计算未受攻击的方块的数量。
  • 处理“进入”和“退出”事件以更新
    slashes
    地图。
  • 如果有“覆盖”事件,则直接进入下一组,因为反斜杠中没有未受攻击的方格。
  • 否则,使用
    slashes
    中的非零条目数来计算反斜杠中未受攻击的方格数。 它是反斜杠对角线的长度减去非零条目的数量。

最后,如果你没有处理最后一个反斜杠 2(m-1),那么使用添加所有未处理的反斜杠中的方格数——它们不会受到攻击。

请注意,问题中的约束表明需要 O(m2)、O(m + n) 或 O(m + n log n) 算法。 这是 O(m log m),这比他们预期的要好。


1
投票

由于对角线具有小范围内的标识数字,因此您可以使用向量而不是集合。索引为对角线编号,对应的值表示对角线是否受到攻击(0或1)。

算法首先迭代前向对角线(/),只有当发现对角线没有受到攻击时,才迭代相关的交叉对角线来统计同样没有受到攻击的对角线。请注意,交叉对角线的数量取决于所考虑的前对角线,并且这些交叉对角线的数量始终相距 2 步(对于给定的前对角线,它们要么都是奇数,要么都是偶数)。

以下是它的编码方式:

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> diagonals(4*n, 1); // initialise with all 1
    
    for (int bishop = 0, row, col; bishop < m; bishop++) {
        std::cin >> row >> col;
        // Mark the two diagonals that this biship covers with 0
        diagonals[row+col] = diagonals[3*n+(row-col)] = 0;
    }
    
    int freeCount = 0;
    for (int forwIdx = 2, lowIdx = 3*n, highIdx = lowIdx; forwIdx <= 2*n; forwIdx++) {
        if (diagonals[forwIdx]) { // Non-attacked diagonal (/)
            // The crossing diagonals (\) always have same parity (+2)
            for (int crossIdx = lowIdx; crossIdx <= highIdx; crossIdx += 2) {
                freeCount += diagonals[crossIdx];
            }
        }
        int grow = forwIdx <= n ? 1 : -1; 
        lowIdx -= grow;
        highIdx+= grow;
    }
    std::cout << freeCount << '\n';
    return 0;
}
© www.soinside.com 2019 - 2024. All rights reserved.