外贸网站模板建设,个人网站源码模板,学校网站建设阶段性目标,广西南宁发现一例题解#xff1a;ABC275 C-Counting Squares
题目
链接#xff1a;Atcoder。
链接#xff1a;洛谷。
难度
算法难度#xff1a;入门。
思维难度#xff1a;普及。
调码难度#xff1a;普及。
综合评价#xff1a;简单。
算法
dfs数论。
思路
由数学方法可严谨…题解ABC275 C-Counting Squares
·题目
链接Atcoder。
链接洛谷。
·难度
算法难度入门。
思维难度普及。
调码难度普及。
综合评价简单。
·算法
dfs数论。
·思路
由数学方法可严谨证明给定四边形其中三个顶点u、v、w当满足以下条件时可添加一个顶点othero使得四边形uvwo为正方形。
条件u.x-v.xv.y-w.yu.y-v.y-(v.x-w.x)||-(u.x-v.x)v.y-w.yu.y-v.yv.x-w.x
可以通过dfs遍历三个顶点判断他们能否构成正方形若可以就通过正方形边长相等的性质求出一个顶点o判断在坐标系中是否存在为“#”的该点若存在则该情况算数否则忽略不计。
最终统计的个数应该除以8再输出因为假设正方形四个顶点分别为ABCD在dfs中会分别遍历它8次。ABC、BCD、CDA、DAB、CBA、DCB、ADC、BAD
·细节
输入字符串时如果不想以0项开始就用以下方式。
方式scanf(%s,字符串名称1);
·代码
今天不做过多解释毕竟有些人只想看空白的代码然后“借鉴也就是copy”一下。
#includebits/stdc.h
using namespace std;
struct Place{int x,y;
};
Place a[20]{};
int ans0;
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 i1;i9;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.xw.x-v.xu.x;ret.yw.y-v.yu.y;if(ret.x1ret.x9ret.y1ret.y9){return ret;}return {0,0};
}
bool be_square(Place u,Place v,Place w){if(u.x-v.xv.y-w.yu.y-v.y-(v.x-w.x)||-(u.x-v.x)v.y-w.yu.y-v.yv.x-w.x){return true;}return false;
}
inline void dfs(int d){if(d4){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 i1;i9;i){for(int j1;j9;j){if(bl[i][j]falsemp[i][j]#){bl[i][j]true;a[d].xi;a[d].yj;dfs(d1);bl[i][j]false;}}}
}
·注意
other函数的边界需要特判。
dfs要回溯。
数学推导不要推理错误。
