首页 > ACM题库 > HDU-杭电 > hdu 3683-gomoku-模拟-[解题报告]hoj
2014
11-30

hdu 3683-gomoku-模拟-[解题报告]hoj

Gomoku

问题描述 :

You are probably not familiar with the title, “Gomoku”, but you must have played it a lot. Gomoku is an abstract strategy board game and is also called Five in a Row, or GoBang. It is traditionally played with go pieces (black and white stones) on a go board (19×19 intersections). Nowadays, standard chessboard of Gomoku has 15×15 intersections. Black plays first, and players alternate in placing a stone of their color on an empty intersection. The winner is the first player to get an unbroken row of five or more stones horizontally, vertically, or diagonally.
To Be an Dream Architect

For convenience, we coordinate the chessboard as illustrated above. The left-bottom intersection is (0,0). And the bottom horizontal edge is x-axis, while the left vertical line is y-axis.

I am a fan of this game, actually. However, I have to admit that I don’t have a sharp mind. So I need a computer program to help me. What I want is quite simple. Given a chess layout, I want to know whether someone can win within 3 moves, assuming both players are clever enough. Take the picture above for example. There are 31 stones on it already, 16 black ones and 15 white ones. Then we know it is white turn. The white player must place a white stone at (5,8). Otherwise, the black player will win next turn. After that, however, the white player also gets a perfect situation that no matter how his opponent moves, he will win at the 3rd move.

So I want a program to do similar things for me. Given the number of stones and positions of them, the program should tell me whose turn it is, and what will happen within 3 moves.

输入:

The input contains no more than 20 cases.
Each case contains n+1 lines which are formatted as follows.
n
x1 y1 c1
x2 y2 c2
……
xn yn cn
The first integer n indicates the number of all stones. n<=222 which means players have enough space to place stones. Then n lines follow. Each line contains three integers: xi and yi and ci. xi and yi are coordinates of the stone, and ci means the color of the stone. If ci=0 the stone is white. If ci=1 the stone is black. It is guaranteed that 0<=xi,yi<=14, and ci=0 or 1. No two stones are placed at the same position. It is also guaranteed that there is no five in a row already, in the given cases.
The input is ended by n=0.

输出:

The input contains no more than 20 cases.
Each case contains n+1 lines which are formatted as follows.
n
x1 y1 c1
x2 y2 c2
……
xn yn cn
The first integer n indicates the number of all stones. n<=222 which means players have enough space to place stones. Then n lines follow. Each line contains three integers: xi and yi and ci. xi and yi are coordinates of the stone, and ci means the color of the stone. If ci=0 the stone is white. If ci=1 the stone is black. It is guaranteed that 0<=xi,yi<=14, and ci=0 or 1. No two stones are placed at the same position. It is also guaranteed that there is no five in a row already, in the given cases.
The input is ended by n=0.

样例输入:

31
3 3 1
3 4 0
3 5 0
3 6 0
4 4 1
4 5 1
4 7 0
5 3 0
5 4 0
5 5 1
5 6 1
5 7 1
5 9 1
6 4 1
6 5 1
6 6 0
6 7 1
6 8 0
6 9 0
7 5 1
7 6 0
7 7 1
7 8 1
7 9 0
8 5 0
8 6 1
8 7 0
8 8 1
8 9 0
9 7 1
10 8 0
1
7 7 1
1
7 7 0
0

样例输出:

Place white at (5,8) to win in 3 moves.
Cannot win in 3 moves.
Invalid.


参考:http://blog.csdn.net/neko01/article/details/40678649


  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  3. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  4. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  5. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  6. #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;
    }

  7. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。