UVA155 All Squares 题解

· · 题解

一次就过的 UVA 灰题

第一眼看见这个题就感觉这题是个搜索题（难度应该橙？）。

但是问题来了，怎么搜索呢？

题目中给的图不是很好看，于是我就自己画了一个：

四种颜色表示不同大小的正方形。

画图的时候，我就发现了一个有趣的事情：

大正方形的 4 个顶点是下一个小正方形的中心。

这个性质题目中也说了：

所有 k>1 的正方形，以其 4 个角为中心点各有一个大小为 k \ div\ 2 的正方形。（在这里 div 指的是整数的除法，例如：9\ div\ 2 = 4）

看图中被我涂黑的 4 个正方形，每个灰色的点既是一个小正方形的中心，又是一个大正方形的顶点。

知道了这个性质，我们就可以轻松的把每个正方形画出来。那么左右正方形所包围的点也能轻而易举地列出来。

AC code:

#include<bits/stdc++.h>
using namespace std;
int k,a,b,ans;
inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void dfs(int x,int y,int k)
{
    if(k==0)
        return ;
    if(x-k<=a&&x+k>=a&&y-k<=b&&y+k>=b)//如果当前的正方形包含这个点
        ans++;
    dfs(x+k,y+k,k/2);//搜索以右下角顶点为中心的下个小正方形
    dfs(x+k,y-k,k/2);//搜索以右上角顶点为中心的下个小正方形
    dfs(x-k,y+k,k/2);//搜索以左下角顶点为中心的下个小正方形
    dfs(x-k,y-k,k/2);//搜索以左上角顶点为中心的下个小正方形
}
int main()
{
    while(true)
    {
        ans=0;
        k=read();
        a=read();
        b=read();
        if(k==0&&a==0&&b==0)
            break;
        dfs(1024,1024,k);//第一个大正方形的中心在(1024，1024)上
        printf("%3d\n", ans);
    }
    return 0;
}

AC记录。