首页 > 代码库 > UVA 12380 Glimmr in Distress --DFS

UVA 12380 Glimmr in Distress --DFS

2024-07-13 09:05:50   222人阅读

题意：给你一串数字序列，只包含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;}
View Code


联系
我们