poj 1691
題目大意：
墻上有一塊區(qū)域被分成了n個矩形，每個矩形要涂上各自的顏色。為了保證完美要求這一塊區(qū)域可以進行涂色的條件是它上方的所有區(qū)域都已經(jīng)涂好顏色，這樣就不會有后續(xù)的操作影響這塊區(qū)域的顏色。但是如果兩塊區(qū)域顏色不同就要換涂顏色用的刷子。問最少需要換幾次。
解題思路：由于這題有一個限制條件，即上方的所有區(qū)域都已經(jīng)涂好顏色，所以肯定是要求一個滿足條件的拓?fù)湫蛄?#xff0c;既然這樣就很好辦了，把上下兩個相鄰的矩形建立一條由上到下的有向邊，然后dfs去搜索滿足條件的拓?fù)湫蛄小?/strong>
AC:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int inf = 0x3f3f3f; struct node {int xl,yl,xr,yr;int c; }rec[20]; struct Edge {int k,next; }edge[50]; int n,cnt,pre[50],indegree[50],ans; bool vis[20];bool cmp(node a,node b) {return a.yl < b.yl; }void addedge(int u,int v) {edge[cnt].k = v;edge[cnt].next = pre[u];pre[u] = cnt++; }void dfs(int cur,int tmp,int dep) {if(dep == n) //所有點都找到{if(tmp < ans) ans = tmp;return;}if(tmp >= ans) return; //當(dāng)前的解大于已知最優(yōu)解for(int i = pre[cur]; i != -1; i = edge[i].next){int k = edge[i].k;indegree[k]--;}for(int i = 1; i <= n; i++){if(vis[i] == true) continue;if(indegree[i] == 0){vis[i] = true;if(rec[i].c != rec[cur].c)dfs(i,tmp+1,dep+1);else dfs(i,tmp,dep+1);vis[i] = false;}}for(int i = pre[cur]; i != -1; i = edge[i].next) //把修改的入度恢復(fù)原狀{int k = edge[i].k;indegree[k]++;} }int main() {int t;scanf("%d",&t);while(t--){memset(pre,-1,sizeof(pre));memset(vis,false,sizeof(vis));memset(indegree,0,sizeof(indegree));cnt = 0;scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d%d%d%d%d",&rec[i].yl,&rec[i].xl,&rec[i].yr,&rec[i].xr,&rec[i].c);sort(rec+1,rec+1+n,cmp);for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++){if(rec[i].yr != rec[j].yl) continue;if(rec[i].xl >= rec[j].xl && rec[i].xr <= rec[j].xr){addedge(i,j);indegree[j]++;}else if(rec[i].xl <= rec[j].xl && rec[i].xr >= rec[j].xr){addedge(i,j);indegree[j]++;}else if(rec[i].xl < rec[j].xr && rec[i].xl > rec[j].xl){addedge(i,j);indegree[j]++;}else if(rec[i].xr < rec[j].xr && rec[i].xr > rec[j].xl){addedge(i,j);indegree[j]++;}}ans = inf;for(int i = 1; i <= n; i++)if(indegree[i] == 0){vis[i] = true;dfs(i,1,1);vis[i] = false;}printf("%d\n",ans);}return 0; }
總結(jié)
- 上一篇： 配置Tomcat使用https协议(配置
- 下一篇： poj 1753