题解：ABC275 C-Counting Squares

·题目

链接：Atcoder。

链接：洛谷。

·难度

算法难度：入门。

思维难度：普及。

调码难度：普及。

综合评价：简单。

·算法

dfs+数论。

·思路

由数学方法可严谨证明，给定四边形其中三个顶点u、v、w，当满足以下条件时，可添加一个顶点other（o）使得四边形uvwo为正方形。

条件：u.x-v.x==v.y-w.y&&u.y-v.y==-(v.x-w.x)||-(u.x-v.x)==v.y-w.y&&u.y-v.y==v.x-w.x

可以通过dfs遍历三个顶点，判断他们能否构成正方形，若可以，就通过正方形边长相等的性质求出一个顶点（o），判断在坐标系中是否存在为“#”的该点，若存在，则该情况算数，否则忽略不计。

最终统计的个数应该除以8再输出，因为假设正方形四个顶点分别为ABCD，在dfs中会分别遍历它8次。（ABC、BCD、CDA、DAB、CBA、DCB、ADC、BAD）

·细节

输入字符串时如果不想以0项开始就用以下方式。

方式：scanf("%s",字符串名称+1);

·代码

今天不做过多解释，毕竟有些人只想看空白的代码，然后“借鉴（也就是copy）”一下。

#include<bits/stdc++.h>
using namespace std;
struct Place{int x,y;
};
Place a[20]={};
int ans=0;
char mp[20][20]={};
bool bl[20][20]={};
Place other(Place u,Place v,Place w);
bool be_square(Place u,Place v,Place w);
inline void dfs(int d);
int main(){for(int i=1;i<=9;i++){scanf("%s",mp[i]+1);}dfs(1);printf("%d\n",ans/8);return 0;
}
Place other(Place u,Place v,Place w){Place ret={};ret.x=w.x-v.x+u.x;ret.y=w.y-v.y+u.y;if(ret.x>=1&&ret.x<=9&&ret.y>=1&&ret.y<=9){return ret;}return {0,0};
}
bool be_square(Place u,Place v,Place w){if(u.x-v.x==v.y-w.y&&u.y-v.y==-(v.x-w.x)||-(u.x-v.x)==v.y-w.y&&u.y-v.y==v.x-w.x){return true;}return false;
}
inline void dfs(int d){if(d==4){if(be_square(a[1],a[2],a[3])==true){if(mp[other(a[1],a[2],a[3]).x][other(a[1],a[2],a[3]).y]=='#'){ans++;a[4]=other(a[1],a[2],a[3]);}}return;}for(int i=1;i<=9;i++){for(int j=1;j<=9;j++){if(bl[i][j]==false&&mp[i][j]=='#'){bl[i][j]=true;a[d].x=i;a[d].y=j;dfs(d+1);bl[i][j]=false;}}}
}

·注意

other函数的边界需要特判。

dfs要回溯。

数学推导不要推理错误。