—— Summon, Light!
0%

hdu 5546 Ancient Go 搜索

发表于 更新于 Valine：

Ancient Go

题意：给出棋盘，轮到 x 这一方下子，问能不能至少提掉一个 o 方的子。
题解：枚举每一个 o ，bfs 一下看看周围的 . 是不是少于等于 1 个，太简单辣！

考虑到要优化时间，枚举每一个 o 的时候直接把那一片 o 都标记了，这样就省了很多次 bfs 。
不得不说这真的是一道打击信心的题。。。。。。
虽然没有WA很多次，，，但是就是想不出来为什么WA。。。
实际上。。。数 . 的时候有些 . 会被数两次。。。比如：

1
2
3
.....xoox
.......ox
.......x.

因为从我的思路来讲，标记一片 o 是为了让下次不再搜索，但是 . 在下次还是会用到的，所以肯定不会标记。这样的后果就是搜索到 . 时其实并不知道它在这一次有没有被搜到过。。。
正确的做法要给 . 加上标记，可以用时间戳标记，代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
char map[10][10];
int b[10][10];
int index;

int bfs(int x,int y)
{
    int res=0;
    queue<PII> Q;
    Q.push(PII(x,y));
    b[x][y]=1;
    while (!Q.empty()) {
        int x=Q.front().first;
        int y=Q.front().second;
        Q.pop();
        for (int i=0;i<4;i++) {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (xx<0||yy<0||xx>=9||yy>=9) continue;
            if (map[xx][yy]=='.') {
                if (b[xx][yy]!=index) {
                    ++res;
                    b[xx][yy]=index;
                }
                /*********WA*********
                ++res;
                ********************/ 
            } else if (map[xx][yy]=='o'&&!b[xx][yy]) {
                b[xx][yy]=1;
                Q.push(PII(xx,yy));
            }
        }
    }
    return res;
}

int main()
{
    int T,t=0;
    scanf("%d",&T);
WCON:
    while (++t<=T) {
        for (int i=0;i<9;i++)
            scanf("%s",map[i]);
        printf("Case #%d: ",t);
        memset(b,0,sizeof(b));
        index=0;
        for (int i=0;i<9;i++) {
            for (int j=0;j<9;j++) {
                if (map[i][j]=='o'&&!b[i][j]) {
                    ++index;
                    int tmp=bfs(i,j);
                    if (tmp<=1) {
                        puts("Can kill in one move!!!");
                        goto WCON;
                    }
                }
            }
        }
        puts("Can not kill in one move!!!");
    }
}

而在我上网查题解的时候又看到了另一种想法

另一种想法

这个想法就回避了数 . 的问题，当然我估计这个想法比较小众。。。因为大家觉得性能太差了。。。
所以说这题。。。出在现场赛还算是公平吧。。。就是太打击信心了 :-( ！！

咖啡，亦我所需也