首页 > 代码库 > UVA 12380 Glimmr in Distress --DFS
UVA 12380 Glimmr in Distress --DFS
题意:给你一串数字序列,只包含0,1,2,一路扫描过去,遇到2则新开一个2x2的矩阵,然后如果扫到0或1就将其填入矩阵,注意不能四个方格全是0或者全是1,那样跟一个方格没区别,所以21111这种是不可能的,问根据串的数字先后顺序可不可能构造一个矩阵出来,正好把数字都填完,如果可以,输出该矩阵的大小,2^n*2^n的形式输出。
分析:其实就是递归求解,首先判断第一个数是不是2,不是则说明没有分块,所以长度必须是1,数字可以为0或1,如果是则dfs,每次遇到2,则dfs下一层,并从下一个下标开始,用flag[4]存储接下来的四个数,以判断是否出现一样的四个数。返回到第0层时,因为第一个数是2,所以j=0的时候就dfs了下去,所以全部符合的话,第0层的j+=1变为1,所以如果第0层j!=1,说明肯定有多的,返回false。
代码:
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define N 2517char ss[N];int now,len,maxi;bool dfs(int dep){ now++; //位置移动 maxi = max(maxi,dep); int j = 0; int tag[4]; memset(tag,-1,sizeof(tag)); for(j=0;j<4&&now<len;j++,now++) { tag[j] = ss[now]-‘0‘; if(tag[j] != 2) continue; if(!dfs(dep+1)) return 0; } if(dep > 0) { if(tag[0] == -1 || tag[1] == -1 || tag[2] == -1 || tag[3] == -1) return 0; if(tag[0] == tag[1] && tag[0] == tag[2] && tag[0] == tag[3] && tag[0] != 2) //四个相同的组成一个 return 0; } else if(j != 1) //dep == 0 return 0; now--; //位置还原 return true;}int main(){ int t,i; scanf("%d",&t); while(t--) { scanf("%s",ss); len = strlen(ss); if(ss[0] != ‘2‘) { if(len != 1) puts("Not Possible"); else puts("2^0*2^0"); } else { maxi = 0; now = -1; if(dfs(0)) printf("2^%d*2^%d\n",maxi,maxi); else puts("Not Possible"); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。