游戏大暴力

发表于 | 分类于 | 阅读次数:
好吧这种题在《论偏题的危害》中被重点批判过……不过还是刷了几道

华容道 huarong

华容道游戏的大模拟，实在变态。不过枚举时候的技巧很不错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map>
typedef long long ll;

const int rm[4]={-1,1,0,0},cm[4]={0,0,-1,1};
const int rn[5][4]={{},{0,0,0,0},{0,0,1,1},{0,0,0,0},{0,1,0,0}},
          cn[5][4]={{},{0,0,0,0},{0,1,0,1},{0,1,0,0},{0,0,0,0}};

int clrtyp[8];

struct S
{
	int mp[7][6];
	S(){memset(mp,-1,sizeof(mp));}
	ll hash()
	{
		int i,j;ll res=0;
		for(i=1;i<=5;i++)
			for(j=1;j<=4;j++)
				res=res*5+clrtyp[mp[i][j]];
		return res;
	}
} stt;

bool operator==(S a,S b)
{
	int i,j;
	for(i=1;i<=5;i++)
		for(j=1;j<=4;j++)
			if(a.mp[i][j]!=b.mp[i][j])
				return false;
	return true;
}

/*const int MAXNODE=1e6+5,MOD=6e6+5;
struct HM
{
	S rsp[MAXNODE];
	int hd[MOD],nxt[MOD],sz;
	void clear(){sz=0,memset(hd,0,sizeof(hd));}
	bool find(S x)
	{
		for(int i=hd[x.hash()%MOD];i;i=nxt[i])
			if(rsp[i]==x) return true;
		return false;
	}
	void push(S x){rsp[++sz]=x,nxt[sz]=hd[x.hash()%MOD],hd[x.hash()%MOD]=sz;}
} hm;*/

bool jud(S a){return a.mp[5][2]==2&&a.mp[4][3]==2;}
bool blkequ(S u,int t,int r,int c,int v)
{
	for(int i=0;i<4;i++)
		if(u.mp[r+rn[t][i]][c+cn[t][i]]!=v)
			return false;
	return true;
}
void blkass(S &u,int t,int r,int c,int v)
{
	for(int i=0;i<4;i++)
		u.mp[r+rn[t][i]][c+cn[t][i]]=v;
}

void bfs()
{
	//hm.clear();
	std::map<ll,bool> hm;
	std::queue<S> queS;
	std::queue<int> quelv;
	queS.push(stt);quelv.push(1);
	hm[stt.hash()]=true;
	while(!queS.empty())
	{
		S u=queS.front();queS.pop();int lv=quelv.front();quelv.pop();
		int i,j,k;
		for(i=1;i<=5;i++) for(j=1;j<=4;j++) if(u.mp[i][j])
		{
			int typ=clrtyp[u.mp[i][j]],clr=u.mp[i][j];
			if(!blkequ(u,typ,i,j,clr)) continue;
			S udel=u;blkass(udel,typ,i,j,0);
			for(k=0;k<4;k++)
			{
				int r=i+rm[k],c=j+cm[k];
				S v=udel;
				if(!blkequ(v,typ,r,c,0)) continue;
				blkass(v,typ,r,c,clr);
				if(!hm[v.hash()])
				{
					hm[v.hash()]=true;
					if(jud(v)) {printf("%d\n",lv);return;}
					queS.push(v);quelv.push(lv+1);
				}
			}
		}
	}
	puts("-1");
}

int main()
{
	freopen("huarong.in","r",stdin);
	freopen("huarong.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--)
	{
		int i,j;
		for(i=1;i<=5;i++)
			for(j=1;j<=4;j++)
				scanf("%d",&stt.mp[i][j]);
		for(i=1;i<=5;i++)
			for(j=1;j<=4;j++)
				if(stt.mp[i][j]>2)
				{
					if(stt.mp[i][j-1]==stt.mp[i][j]||stt.mp[i][j-1]==stt.mp[i][j])
						clrtyp[stt.mp[i][j]]=3;
					else clrtyp[stt.mp[i][j]]=4;
				}
		clrtyp[0]=0,clrtyp[1]=1,clrtyp[2]=2;
		if(jud(stt)) {puts("0");continue;}
		bfs();
	}
	return 0;
}

[NOIP2015]斗地主

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstdio>
#include<cstring>

int n;

int num[20],numcnt[20];

int calc(int t1,int n1,int t2,int n2)
{
    int res=0;
    while(numcnt[t1]>=n1&&numcnt[t2]>=n2) numcnt[t1]-=n1,numcnt[t2]-=n2,res++;
    return res;
}
int calRst()
{
    int res=0;
    memset(numcnt,0,sizeof(numcnt));
    for(int i=3;i<=16;i++) numcnt[num[i]]++;
    res+=calc(4,1,2,2);res+=calc(4,1,1,2);res+=calc(3,1,2,1);res+=calc(3,1,1,1);
    res+=numcnt[4]+numcnt[3]+numcnt[2]+numcnt[1];
    return res;
}
int ans;
void dfs(int lv)
{
    if(lv>=ans) return;
    int i,typ,l,r;
    for(typ=1;typ<=3;typ++)
        for(l=3;l<=13;l++)
        {
            r=l-1;while(num[r+1]>=typ&&r+1<=14) r++;
            int len=r-l+1;
            if(len<=(1<<3-typ)) continue;
            for(i=l;i<l+(1<<3-typ);i++) num[i]-=typ;
            for(i=l+(1<<3-typ);i<=r;i++)
            {
                num[i]-=typ;
                dfs(lv+1);
            }
            for(i=l;i<=r;i++) num[i]+=typ;
        }
    ans=std::min(ans,lv+calRst());
}

int main()
{
    int T;scanf("%d%d",&T,&n);
    while(T--)
    {
        memset(num,0,sizeof(num));
        int i,a,b;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            if(a==1) a=14;if(a==2) a=15;if(a==0) a=16;
            num[a]++;
        }    
        ans=std::min(n,13);
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}

[NOIP2012]Mayan 游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<iostream>
#include<cstdio>
#include<cstring>

int n;
struct O{int x,y;bool g;} opt[6];

struct M
{
    int mp[7][5];M(){memset(mp,0,sizeof(mp));}
    bool empty()
    {
        int r,c;
        for(r=0;r<7;r++) for(c=0;c<5;c++)
            if(mp[r][c]) return false;
        return true;
    }
    void fallDown()
    {
        int r,c;
        for(c=0;c<5;c++)
        {
            int cnt=0;
            for(r=0;r<7;r++) if(mp[r][c])
                std::swap(mp[cnt++][c],mp[r][c]);
        }
    }
    bool clear()
    {
        int r,c;
        bool clrd[7][5];memset(clrd,false,sizeof(clrd));
        for(r=0;r<7;r++) for(c=0;c<5;c++)
        {
            if(c<3&&mp[r][c]&&mp[r][c]==mp[r][c+1]&&mp[r][c+1]==mp[r][c+2])
                clrd[r][c]=clrd[r][c+1]=clrd[r][c+2]=true;
            if(r<5&&mp[r][c]&&mp[r][c]==mp[r+1][c]&&mp[r+1][c]==mp[r+2][c])
                clrd[r][c]=clrd[r+1][c]=clrd[r+2][c]=true;
        }
        bool res=false;
        for(r=0;r<7;r++) for(c=0;c<5;c++)
            if(clrd[r][c]) mp[r][c]=0,res=true;
        return res;
    }
    int *operator[](const int r){return mp[r];}
    M *operator=(const M &ot){memcpy(this->mp,ot.mp,sizeof(ot.mp));return this;}
};

bool ok;
void dfs(int lv,M u)
{
    int i;
    if(lv>n)
    {
        if(u.empty())
        {
            for(i=1;i<=n;i++)
                printf("%d %d %d\n",opt[i].x,opt[i].y,opt[i].g?1:-1);
            ok=true;
        }
        return;
    }
    int r,c;
    int num[11];memset(num,0,sizeof(num));
    for(r=0;r<7;r++) for(c=0;c<5;c++) num[u[r][c]]++;
    for(i=1;i<=10;i++) if(num[i]&&num[i]<3) return;
    for(c=0;c<4;c++) for(r=0;r<7;r++)
        if(u[r][c]!=u[r][c+1])
        {
            if(u[r][c]) opt[lv]=(O){c,r,true};
            else opt[lv]=(O){c+1,r,false};
            M v=u;
            std::swap(v[r][c],v[r][c+1]);
            do v.fallDown();while(v.clear());
            dfs(lv+1,v);
            if(ok) return;
        }
}

int main()
{
    scanf("%d",&n);
    M mp;
    for(int c=0;c<5;c++)
    {
        int clr,r=0;
        while(scanf("%d",&clr)&&clr)
            mp[r++][c]=clr;    
    }
    dfs(1,mp);
    if(!ok) puts("-1");
    return 0;
}