题目地址：点击打开链接
题意：给你很多齿轮，让你判断第一个齿轮和第n个齿轮的关系。有三种关系题目中已经给出。
解题思路：算是比较直观的一个dfs题目了，重点是怎么样处理这个dfs。
结合题目中给出的正负关系，我们可以联想到齿轮的方向，于是我们有了以下处理方式：
<1>: 如果有一个齿轮和第一个齿轮相连并且转动方向相同，那么这个第一个齿轮无法转动。
<2>:如果第一个齿轮没法通过其他齿轮与第n个齿轮相连，那么就输出The input gear is not connected to the output gear.
<3>:如果满组题目要求的话，就可以解决问题了。
那么我们怎样处理dfs呢，根据以上所说，关键是处理方向，这里我们用+1，-1，0，来表示齿轮的三种状态。
在dfs是加以判断就可以了。
上代码：
#include<cstdio>
int n;
struct gear { int x, y, r; } a[1024];
int dir[1024];
int gcd(int x, int y)
{
return y==0? x : gcd(y,x%y);
}
bool solve(int i, int d)
{
dir[i] = d;
for (int j = 1; j <= n; j++)
{
if (i != j && (a[i].x - a[j].x)*(a[i].x - a[j].x)
+ (a[i].y - a[j].y)*(a[i].y - a[j].y)
== (a[i].r + a[j].r)*(a[i].r + a[j].r))// 判断齿轮是否相连
{
if (dir[i] == dir[j]) return false;// 如果同向，则无法转动
if (dir[j]) continue;
if (!solve(j, -d)) return false;// 递归实现
}
}
return true;
}
int main()
{
int i;
scanf("%d", &n);
for (i = 1; i <= n; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
if (!solve(1, 1)) printf("The input gear cannot move.\n");
else if (!dir[n]) printf("The input gear is not connected to the output gear.\n");
else
{
int g = gcd(a[1].r, a[n].r);
printf("%d:%d\n", a[1].r*dir[n] / g, a[n].r / g);
}
return 0;
}
水波。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
