首页 > 搜索 > DFS搜索 > HDU 1809 A New Tetris Game(2)-DFS-[解题报告] C++
2013
12-23

HDU 1809 A New Tetris Game(2)-DFS-[解题报告] C++

A New Tetris Game(2)

问题描述 :

自从Lele发明了新的类俄罗斯游戏 A New Tetris Game 后,他整日整夜得玩,现在渐渐的,他发现这个游戏也不过如此,为了加大点难度,他制定了一套新的规则:

首先,Lele和姐姐拿出N个长方形的棋盘,这些棋盘中有些格子是不可用的,剩下的都是可用的。每次Lele和姐姐轮流从N个棋盘里选出一个棋盘,拿出俄罗斯方块里的正方形方块(大小为2*2的正方形方块)往这个棋盘里放,要注意的是,放进去的正方形方块不能叠在棋盘不可用的格子上,也不能叠在已经放了的正方形方块上。
到最后,谁不能再放正方形方块,谁就输了。

现在,假设每次Lele和姐姐都很聪明,都能按最优策略放正方形,并且每次都是Lele先放正方形,你能告诉他他是否一定能赢姐姐吗?

输入:

本题目包含多组测试,请处理到文件结束。
每组测试第一行包含一个正整数N(N<30),表示棋盘的输个数
接下来有N个棋盘的描述。
对于每个棋盘,第一行有两个整数R,C(R*C<50),分别表示棋盘的行数和列数。然后有R行,每行C个字符来表示这个棋盘。
其中0是代表棋盘该位置可用,1是代表棋盘该位置不可用

你可以假设,每个棋盘中,0的个数不会超过40个。

输出:

对于每一组测试,如果Lele有把握获胜的话,在一行里面输出"Yes",否则输出"No"。

样例输入:

2
4 4
0000
0000
0000
0000
4 4
0000
0010
0100
0000
1
4 4
0000
0010
0100
0000

样例输出:

Yes
No

http://acm.hdu.edu.cn/showproblem.php?pid=1809

这个题是 “A New Tetris Game” 的升级版

第一 需要用SG处理

第二 需要记录状态

由于有多个棋盘 所以要对应到 S-Nim 里面的值  

而且数据变多了 简单的dfs会超时,需要记录状态,我是用map< , >来记录的 

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<algorithm>
#include<cmath>

using namespace std;
//#pragma comment(linker,"/STACK:1000000000,1000000000")

#define LL long long

const int N=55;
string s;
map<string,int>str;
int n,m;
int dfs()
{
    map<string,int>::iterator it;
    it=str.find(s);
    if(it!=str.end())
    return (it->second);
    bool visited[12];
    memset(visited,false,sizeof(visited));
    for(int i=1;i<n;++i)
    {
        for(int j=0;j<m-1;++j)
        {
            if(s[i*m+j]=='1'||s[(i-1)*m+j]=='1'||s[i*m+j+1]=='1'||s[(i-1)*m+j+1]=='1')
            continue;
            s[i*m+j]='1';s[(i-1)*m+j]='1';s[i*m+j+1]='1';s[(i-1)*m+j+1]='1';
            visited[dfs()]=true;
            s[i*m+j]='0';s[(i-1)*m+j]='0';s[i*m+j+1]='0';s[(i-1)*m+j+1]='0';
        }
    }
    for(int i=0;i<=11;++i)
    if(!visited[i])
    {str[s]=i;return i;}
}
int main()
{
    //freopen("data.txt","r",stdin);
    int T;
    while(scanf("%d",&T)!=EOF)
    {
        int k=0;
        while(T--)
        {
            scanf("%d %d",&n,&m);
            str.clear();
            s.clear();
            string a;
            for(int i=0;i<n;++i)
            {
                cin>>a;
                s+=a;
            }
            //cout<<s<<endl;
            k=(k^dfs());
        }
        if(k)
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

  

解题报告转自:http://www.cnblogs.com/liulangye/archive/2012/10/17/2727348.html


,
  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的