题解：ABC275 C-Counting Squares
题解：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要回溯。
数学推导不要推理错误。