【POJ 1691 Painting A Board】【 luoguP1283 平板涂色】【 #10023. 「一本通 1.3 练习 2」平板涂色】搜索

文章图片

文章图片

文章图片

直接爆搜即可...

#include #include #include #include #define N 22 #define COL 25using namespace std; inline int wread(){ char c=getchar (); int flag=1,wans=0; while (c<'0'||c>'9'){if (c=='-') flag=-1; c=getchar (); } while (c>='0'&&c<='9'){wans=wans*10+c-'0'; c=getchar (); } return wans*=flag; }int n; struct node {int ya,xa,yb,xb,col,num; }a[N]; int cnt[N][N],top[N]; //cnt[i][j] 表示第i个矩形需要的第j个矩形先被涂色 bool vis[N]; int acce[N]; int belcol[COL][N],topcol[COL]; //belcol[i][j] 表示第i种颜色的第j个矩形的编号 //topcol[i] 表示第i种颜色的个数 int ans=0x3f3f3f3f; void dfs (int nx,int sum){ if (sum>=ans) return ; if (nx==n) {ans=min (ans,sum); return ; } for (int A=1; A<=n; ++A){ if (vis[A]) continue; bool F=true; for (int B=1; B<=top[A]; ++B){ int nd(cnt[A][B]); if (!vis[nd]) {F=false; break; } } if (!F) continue; int H(1); int nxcol(a[A].col); vis[A]=true; int sav[N],savtop(0); sav[++savtop]=A; for (int i=1; i<=topcol[nxcol]; ++i){ int bian(belcol[nxcol][i]); if (vis[bian]) continue; bool jud=true; for (int j=1; j<=top[bian]; ++j){ int nd(cnt[bian][j]); if (!vis[nd]) {jud=false; break; } } if (!jud) break; sav[++savtop]=bian; vis[bian]=true; H++; } dfs (nx+H,sum+1); for (int i=1; i<=savtop; ++i) vis[i]=false; } }int main (){ n=wread(); for (int i=1; i<=n; ++i){a[i].ya=wread(); a[i].xa=wread(); a[i].yb=wread(); a[i].xb=wread(); a[i].col=wread(); a[i].num=i; } int acc=0; for (int i=1; i<=n; ++i){ for (int j=1; j<=n; ++j){ if (i==j) continue; if (a[i].ya==a[j].yb && a[j].xa<=a[i].xb) cnt[i][++top[i]] = j; } if (!top[i]) acce[++acc]=i; belcol[a[i].col][++topcol[a[i].col]]=i; } for (int A=1; A<=acc; ++A){ memset (vis,false,sizeof vis); int H(0); int x=acce[A]; //编号 vis[x]=true; H++; int nxcol(a[x].col); for (int i=1; i<=topcol[nxcol]; ++i){ int bian(belcol[nxcol][i]); if (vis[bian]) continue; bool jud=true; for (int j=1; j<=top[bian]; ++j){ int nd(cnt[bian][j]); if (!vis[nd]) {jud=false; break; } } if (!jud) continue; vis[bian]=true; H++; } dfs (H,1); } printf("%d\n",ans); return 0; }

总结：
【【POJ 1691 Painting A Board】【 luoguP1283 平板涂色】【 #10023. 「一本通 1.3 练习 2」平板涂色】】1. 细节问题（可就是不想多检查，这是为什么呢，NOIP考场可咋办）