题目：
The Great Revegetation
(grass.cpp/in/out 1s 256M)
长时间的干旱使得Farmer John的N块草地上牧草匮乏。随着雨季即将到来，现在应当是重新种植的时候了。在Farm
er John的储物棚里有四个桶，每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶
农，Farmer John想要确保他的每头奶牛都能得到丰富的食谱。他的M头奶牛每一头都有两块喜爱的草地，他想要确
保这两块草地种植不同种类的草，从而每头奶牛都可以有两种草可供选择。Farmer John知道没有一块草地受到多
于3头奶牛的喜爱。
请帮助Farmer John选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
Input
输入的第一行包含N（2≤N≤100）和M（1≤M≤150）。
以下M行，每行包含两个范围为1…N的整数，为Farmer John的一头奶牛喜欢的两块草地。
Output
输出一个N位数，每一位均为1…4之一，表示每一块草地上所种的草的种类。
第一位对应草地1的草的种类，第二位对应草地2，以此类推。如果有多种可行的解，只需输出所有解中最小的N位数。
Sample Input
5 6
4 1
4 2
4 3
2 5
1 2
1 5
Sample Output
12133
法一：
递归dfs，不断查找当前位数可摆放的最小值。
先排序，保证从上到下，从左至右为递增状态。
k表示位数，side表示当前可摆放的最小值
flag[k][i]表示第k位上能否放i这个数
如果左边的值已经放好了，那么右边的就不能放左边的值了，flag[node[u].y][ans]=false;
因为草地的种类和在[1,N]之间，所以判断当前最小值是否为当前的位数(保证第一位即为1)
code:
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define fill(a,b) memset(a,b,sizeof(a)) 4 using namespace std; 5 bool flag[2100][5]; 6 int n,m; 7 struct kk{int x,y;}node[2100]; 8 int cmp(kk A,kk B){return A.x<B.x;} 9 void dfs(int k,int side){ 10 int u=0,ans; 11 if (k>n) return ; 12 for (int i=1;i<=4;i++) 13 if (flag[k][i]){ans=i;break;} 14 printf("%d",ans); 15 for (u=side;node[u].x==k;u++){ 16 flag[node[u].y][ans]=false; 17 } 18 dfs(k+1,u); 19 } 20 int main(){ 21 //freopen("grass.in","r",stdin); 22 //freopen("grass.out","w",stdout); 23 scanf("%d%d",&n,&m); 24 fill(flag,true); 25 for (int i=1;i<=m;i++){ 26 scanf("%d%d",&node[i].x,&node[i].y); 27 if (node[i].x>node[i].y) swap(node[i].x,node[i].y); 28 } 29 sort(node+1,node+m+1,cmp); 30 dfs(1,1); 31 return 0; 32 }/* 33 6 6 34 1 2 35 2 3 36 3 4 37 4 5 38 1 5 39 1 6 40 */
法二：
类似于法一，之间三个for循环模拟
code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int N, M; 6 int A[151], B[151], G[101]; 7 cin >> N >> M; 8 for (int i=0; i<M; i++) { 9 cin >> A[i] >> B[i]; 10 if (A[i] > B[i]) swap (A[i], B[i]); 11 } 12 for (int i=1; i<=N; i++) { 13 int g; 14 for (g = 1; g <= 4; g++) { 15 bool ok = true; 16 for (int j=0; j<M; j++){ 17 if (B[j] == i && G[A[j]] == g){ 18 ok = false; 19 20 } 21 //cout<<"G[A[j]]= "<<G[A[j]]<<" g= "<<g<<" i= "<<i<<" j= "<<j<<" A[j]= "<<A[j]<<" B[j]= "<<B[j]<<endl; 22 } 23 if (ok) break; 24 } 25 G[i] = g; 26 //cout<<"G[i]= "<<G[i]<<endl; 27 cout << g; 28 } 29 cout << "\n"; 30 return 0; 31 }