问题分析

这是一个关于移动电话中继塔频率分配的问题。当移动电话的中继塔与所在区域的移动电话进行通信时，为避免干扰，相邻的中继塔所分配的频率差值至少为 2 ，并且要使用尽可能少的频率来为这些中继塔分配频率。代码的任务是根据给定的中继塔坐标，判断并输出最少需要多少种频率来满足分配要求。

代码整体思路

代码首先读取中继塔的数量和坐标，然后根据坐标计算出哪些中继塔是相邻的（距离不超过 20 ，即距离的平方不超过 400 ），并将相邻关系记录在邻接矩阵 g 中。接着通过深度优先搜索（DFS）尝试用不同数量的频率（从 1 到 4 ）对中继塔进行染色（分配频率），找到满足条件的最少频率数量并输出。

详细代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int num; 
int n;
int g[40][40];
double x[40];
double y[40];
int color[40];
bool dfs(int i)
{
	for(int c=1;c<=num;c++)
	{
		int flag=0;
		for(int j=0;j<n;j++)
		{
			if(g[j][i]==1 && color[j]==c)
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			color[i]=c;
			if(i==n-1)
			{
				return true;
			}
			return dfs(i+1);
			color[i]=0;
		}
	}
	return false;
}
int main()
{
	int tag=0;
	while(1)
	{
		tag++;
		cin>>n;
		if(n==0)
		{
			break;
		}
		memset(g,0,sizeof(g));
		for(int i=0;i<n;i++)
		{
			cin>>x[i]>>y[i];
		} 
		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=400)
				{
					g[i][j]=g[j][i]=1;
				}
			}
		}
		for(num=1;num<=4;num++)
		{
			memset(color,0,sizeof(color));
			if(dfs(0))
			{
				printf("The towers in case %d can be covered in %d frequencies.\n",tag,num);
				break;
			}
		}
	} 
	return 0;
}