題解 P3717 【[AHOI2017國中組]cover】

題目連結

本題的大緻思路就是搜尋。

将矩陣初始化成false。先把燈塔标記。在搜一遍燈塔能照到的點并标記。最後搜一遍找被燈塔标記的個數。

詳細解釋見題解。

題解走起。

#include<bits/stdc++.h>
using namespace std;
bool a[1001][1001];                                  //數組開的有點大哈，開到200就足夠了。不過想要标記，就要是bool型的。
int main()
{
    int n,m,r,sum=0;                                 //sum為後面用的計數器。
    int j=0,k=0,i=0;
    int x,y;                                           //i,j,k,x,y作為控制循環次數的東東。
    cin>>n>>m>>r;                                    //輸入資料
    for(i=0;i<m;i++)                                 //第一遍标記###看好括号###
    {
        cin>>j>>k;                                   //對于每一個燈塔的坐标進行輸入
        a[j-1][k-1]=1;                               //标記燈塔位置
                                                     /*這裡要說一點，燈塔坐标給的和數組定義的不太一樣。
                                                       數組的0是第一位。而燈塔的坐标是從1開始的，是以要将坐減一。
                                                       我第一次就是這麼被坑的。*/
        for(x=0;x<n;x++)                             //第一次搜尋開始
        {   for(y=0;y<n;y++)
            {
              if((x-j+1)*(x-j+1)+(y-k+1)*(y-k+1)<=r*r)//圓的方程：(x-a)²+(y-b)²=r²
              {
                  a[x][y]=1;                         //标記被搜到的。
              }
            }
        }                                            //說實話這個括号和上面“第二次搜尋開始“後面的都不用加。
                                                     //為了清楚，我現在加上了。
    }                                                //好了，現在搜完第一次了
                                                     //開始統計。第二次搜尋，并計數
    for(i=0;i<n;i++)                                 //全圖走一遍。
    {   for(j=0;j<n;j++)
        {
            if(a[i][j]==1)
            {
                sum++;
            }
        }   
    }
    cout<<sum;                                       //輸出
    return 0;                                        //程式拜拜。
}