POJ 1129 (dfs)

2019-11-06 07:44:15

字体：大中小

来源：转载

供稿：网友

题意	思路
基本涂色问题：这里给出字母A~Z和每个字母相邻的字母，问最少需要需要多少要颜色才能满足	思路是：dfs，要注意的是每次dfs是做什么的，要有明确的目的才不会出错。

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int M = 30;int isfind;int color[M];int gragh[M][M];int ans;int n;int ok(int id,int x) //查找相邻的点用的是否用的一个颜色{ for(int i = 0;i < n; i++) { if(gragh[id][i] && color[i] == x) return false; } return true;}void dfs(int id,int num){ if(isfind) return ; if(id == n) { isfind = true; return ; } for(int i = 1;i <= num; i++) { if(ok(id,i)) { color[id] = i; dfs(id+1,num); } } if(isfind == 0) { ans++; dfs(id,ans); }}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d",&n) != EOF && n) { memset(color,0,sizeof(color)); memset(gragh,0,sizeof(gragh)); for(int i = 0;i < n; i++) { char s[1000]; scanf("%s",s); int length = strlen(s); for(int j = 2;j < length; j++) { gragh[s[0]-'A'][s[j]-'A'] = true; } } isfind = false; ans = 1; dfs(0,1); if(ans == 1) { PRintf("1 channel needed./n"); } else { printf("%d channels needed./n",ans); } } return 0;}

上一篇：SDRAM理论篇之基础知识及操作时序讲解

下一篇：PIC单片机-步进电机的正转与反转