不充錢，你怎么AC？

　　題目：http://codevs.cn/problem/1116/

?

　　數(shù)據(jù)很小，DFS可A，每層枚舉顏色，判斷相鄰的點(diǎn)是否有重復(fù)的顏色，記得回溯時(shí)把顏色染回0，即無顏色

　　這里我使用了一個(gè)優(yōu)化，在讀入的時(shí)候?qū)⑾噜彽狞c(diǎn)壓入數(shù)組，這樣在判斷的時(shí)候時(shí)間就小于O(n)

　　不過這個(gè)優(yōu)化好像沒有不回溯的方法好，然而并沒有寫不回溯的

 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hadilo/p/5903621.html

總結(jié)

以上是生活随笔為你收集整理的[ CodeVS冲杯之路 ] P1116的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。