首页 > 搜索 > DFS搜索 > HDU 1760 A New Tetris Game-博弈-[解题报告] C++
2013
12-23

HDU 1760 A New Tetris Game-博弈-[解题报告] C++

A New Tetris Game

问题描述 :

曾经,Lele和他姐姐最喜欢,玩得最久的游戏就是俄罗斯方块(Tetris)了。
渐渐得,Lele发觉,玩这个游戏只需要手快而已,几乎不用经过大脑思考。
所以,Lele想出一个新的玩法。

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

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

输入:

本题目包含多组测试,请处理到文件结束。
每组测试第一行包含两个正整数N和M(0<N*M<50)分别代表棋盘的行数和列数。
接下来有N行,每行M个0或1的数字代表整个棋盘。
其中0是代表棋盘该位置可用,1是代表棋盘该位置不可用

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

输出:

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

样例输入:

4 4
0000
0000
0000
0000
4 4
0000
0010
0100
0000

样例输出:

Yes
No

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

题意:出处http://blog.csdn.net/qiqijianglu/article/details/7952261

题意:给你一个n*m的矩形,0表示空着的,1反之,现在两个人轮流放2*2的矩形,谁不能放了,谁就输了。
找sg值,可以选择暴力,也可以利用sg值的特点简化。
暴力就跟取石子一样,没什么差别,DFS搞定。把矩阵看成一个字符串,字符串就是一个状态。
其实我们也可以不暴力求sg值,因为只要当前状态能到达一个sg值为0的点,当前状态就是必胜点。
若当前点到达的所有状态都是必胜的,那么当前点就是必败点。所以当我们到达必胜点时,就必须转换当前状态继续递归找sg值。
法一、暴力找sg值:
 
表示还在理解中。。。。n

 

// I'm lanjiangzhou
//C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
//C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cctype>
#include <stack>
#include <string>
#include <list>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <set>
using namespace std;

//*************************OUTPUT*************************
#ifdef WIN32
#define INT64 "%I64d"
#define UINT64 "%I64u"
#else
#define INT64 "%lld"
#define UINT64 "%llu"
#endif

//**************************CONSTANT***********************
#define INF 0x3f3f3f3f

// aply for the memory of the stack
//#pragma comment (linker, "/STACK:1024000000,1024000000")
//end

int n,m;
const int maxn =110;
char s[maxn][maxn];
int a[maxn][maxn];
int mm[maxn][maxn];

int findset(int mm[maxn][maxn]){
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m-1;j++){
            if(mm[i][j]+mm[i+1][j]+mm[i][j+1]+mm[i+1][j+1]==0){
                int tt[maxn][maxn];
                for(int x=0;x<n;x++){
                    for(int y=0;y<m;y++){
                        tt[x][y]=mm[x][y];
                    }
                }
                tt[i][j]=tt[i+1][j]=tt[i][j+1]=tt[i+1][j+1]=1;
                if(findset(tt)==0) return 1;
            }
        }
    }
    return 0;
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        //getchar();
        for(int i=0;i<n;i++){
            scanf("%s",s[i]);
            for(int j=0;j<m;j++)
                a[i][j]=s[i][j]-'0';
        }
        if(findset(a)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

 

解题报告转自:http://www.cnblogs.com/lanjiangzhou/archive/2013/04/14/3021130.html


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  3. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept