Blog·Tanky WooABOUTRSS

HDU/HDOJ 1175 连连看[BFS]

25 Jun 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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

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

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

AC代码:

#include 
#include 
#include 
#include 
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 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;
}