HDU/HDOJ 1175 连连看[BFS]

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1175

BFS,如果用纯BFS会超时,剪枝,增加一个数组rec[][]保存当前点的最小转折点,这样可以剪去很多不必要的路径。

这题很BUG,因为我的int dir[4][2] = {{}, {}, {}, {}}的4个方向顺序不同,时间相差数倍,我用上下左右来写,超时,我找了一个多小时,换了一个方向,结果就只要3000ms了,真是无语了~~~

AC代码:

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
#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 99;
 
int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; // up, down, left, right
int n, m, q;
int map[1005][1005];  // 保存输入的值
int rec[1005][1005];
int sx, sy, ex, ey;
bool flag;
 
typedef struct node{
    int x, y;
    int turn;
    int d;
}node;
node start;
 
queue<node> que;
 
inline bool isIn(const node &p){
     if(p.x<1 || p.y<1 || p.x>n || p.y>m)
         return false;
     return true;
 }
 
 
void BFS()
{
    node now, tmp;
    while(!que.empty())
    {
        now = que.front();
        que.pop();
        if(now.x == ex && now.y == ey && now.turn <= 2)
        {
            flag = true;
            return;
        }
        for(int i=0; i<4; ++i)
        {
            tmp.x = now.x + dir[i][0];
            tmp.y = now.y + dir[i][1];
            if(now.d == i)
            {
                tmp.turn = now.turn;
                tmp.d = i;
            }
            else
            {
                tmp.turn = now.turn + 1;
                tmp.d = i;
            }
            if(isIn(tmp) && (map[tmp.x][tmp.y]==0||tmp.x==ex&&tmp.y==ey) && rec[tmp.x][tmp.y] >= tmp.turn)
            {
                rec[tmp.x][tmp.y] = tmp.turn;
                que.push(tmp);
            }
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    while(scanf("%d %d", &n, &m))
    {
        if(n == 0 && m == 0)
            break;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=m; ++j)
                scanf("%d", &map[i][j]);
        //cin >> q;
        scanf("%d", &q);
        while(q--)
        {
            //cin >> sx >> sy >> ex >> ey;
            scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
            //memset(rec, INF, sizeof(rec));
 
            // 判断两点的值不相同,或其中一点值为0,或者两点是同一点,此时直接判为NO
            if((map[sx][sy] != map[ex][ey])
                || (map[sx][sy] == 0)
                || (map[ex][ey] == 0)
                || (sx==ex && sy==ey))
            {
                cout << "NO\n";
                continue;
            }
            //------------
            // 清空队列que
            while(!que.empty())
                que.pop();
            // 初始条件,加入队列que
            for(int i=0; i<4; ++i)
            {
                start.x = sx;
                start.y = sy;
                start.turn = 0;
                start.d = i;
                que.push(start);
            }
 
            for(int i=1; i<=n; ++i)
                for(int j=1; j<=m; ++j)
                    rec[i][j] = 11;
 
            flag = false;
            rec[sx][sy] = 0;
            BFS();
            if(flag)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1175 连连看[BFS]》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注