首页 > 代码库 > [ CodeVS冲杯之路 ] P1116
[ CodeVS冲杯之路 ] P1116
不充钱，你怎么AC？
题目：http://codevs.cn/problem/1116/
数据很小，DFS可A，每层枚举颜色，判断相邻的点是否有重复的颜色，记得回溯时把颜色染回0，即无颜色
这里我使用了一个优化，在读入的时候将相邻的点压入数组，这样在判断的时候时间就小于O(n)
不过这个优化好像没有不回溯的方法好，然而并没有写不回溯的
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 const int N=10;10 int a[N],f[N][N],n,ans;11 void dfs(int x)12 {13 if (x>n)14 {15 ans++;16 return;17 }18 int i,j;19 for (i=1;i<=4;i++)20 {21 for (j=1;j<=f[x][0];j++) if (a[f[x][j]]==i) break;22 if (j<=f[x][0]) continue;23 a[x]=i;24 dfs(x+1);25 a[x]=0;26 }27 }28 int main()29 {30 int i,x,j;31 scanf("%d",&n);32 for (i=1;i<=n;i++)33 for (j=1;j<=n;j++)34 {35 scanf("%d",&x);36 if (x) f[i][++f[i][0]]=j;37 }38 dfs(1);39 printf("%d\n",ans);40 return 0;41 }
[ CodeVS冲杯之路 ] P1116
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。