The 36th ACM/ICPC Asia Regional Shanghai Site —— Warmup题目链接 ：?pid=4012题目大意：给你一个2 * n的矩阵，给里面的子矩阵涂色，每次涂一种颜色，同一个区域被涂两次则第一次涂的会被第二次覆盖，求最少要涂几次能达到目标状态题目分析：因为其中状态很多而n又不大，考虑采用状压搜索，，把每种状态都加入队列，一个vis[1 << 16]数组标记每一位的状态，如果是1表示该位置已经是目标色，0则表示还未涂色，状态有很多种，一共分成6类，第一行左右扩展，第二行左右扩展，第一行第二行共同左右扩展，注意一些剪枝，详细见程序注释#include <cstdio>#include <cstring>#include <queue>using namespace std;struct NODE{int val;int step;};bool vis[1 << 16]; //标记各位置是否达到目标色char s[20];int n;int BFS(){queue<NODE> q;NODE st, cur, next;memset(vis, false, sizeof(vis));vis[0] = true;st.val = 0;st.step = 0;q.push(st);while(!q.empty()){cur = q.front();q.pop();//各位都为1则涂色完成if(cur.val == (1 << 2 * n) – 1)return cur.step;for(int i = 0; i < 2 * n; i++){//如果当前位置已经涂色，则不作为拓展原点if((1 << i) & cur.val)continue;next = cur;next.step ++;int tmp = 0;//单行向右扩展int nn = i < n ? n : 2 * n;for(int j = i; j < nn; j++){//若该点已经涂色则退出循环if((1 << j) & cur.val)break;//若该点未涂色且颜色和目标色相同则上色if(s[j] == s[i])tmp = tmp | (1 << j);}//单行向左扩展nn = i < n ? 0 : n;for(int j = i – 1; j >= nn; j–){if((1 << j) & cur.val)break;if(s[j] == s[i])tmp = tmp | (1 << j);}//将所有状态分离，若出现新的状态则加入队列for(int j = tmp; j; j = tmp & (j – 1)){int val = cur.val | j;if(!vis[val]){vis[val] = true;next.val = val;q.push(next);}}//双行扩展通过第一行来得到第二行，若当前对应//的第二行的位置已经涂色，则该列不作为拓展原点if(i >= n || (cur.val & (1 << i + n)))continue;tmp = 0;for(int j = i; j < n; j++){if(((1 << j) & cur.val) || ((1 << (j + n)) & cur.val))break;if(s[j] == s[i])tmp |= (1 << j);if(s[j + n] == s[i])tmp |= (1 << (j + n));}for(int j = i – 1; j >= 0; j–){if(((1 << j) & cur.val) || ((1 << (j + n)) & cur.val))break;if(s[j] == s[i])tmp |= (1 << j);if(s[j + n] == s[i])tmp |= (1 << (j + n));}for(int j = tmp; j; j = tmp & (j – 1)){int val = cur.val | j;if(!vis[val]){vis[val] = true;next.val = val;q.push(next);}}}}return 0;}int main(){int T;scanf("%d", &T);for(int ca = 1; ca <= T; ca++){scanf("%d", &n);scanf("%s %s", s, s + n); //将两行读做一行printf("Case #%d: %d\n", ca, BFS());}}
只能昏昏沉沉地沿着青草和泥土的气息前进。
