连连看-HDU1175

文章目录
  1. 1. 连连看
  2. 2. 思路
  3. 3. AC代码
  4. 4. 扩展

连连看

“连连看”相信很多人都玩过。没玩过也没关系,下面我给大家介绍一下游戏规则:在一个棋盘中,放了很多的棋子。如果某两个相同的棋子,可以通过一条线连起来(这条线不能经过其它棋子),而且线的转折次数不超过两次,那么这两个棋子就可以在棋盘上消去。不好意思,由于我以前没有玩过连连看,咨询了同学的意见,连线不能从外面绕过去的,但事实上这是错的。现在已经酿成大祸,就只能将错就错了,连线不能从外围绕过。
玩家鼠标先后点击两块棋子,试图将他们消去,然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。

输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000),分别表示棋盘的行数与列数。在接下来的n行中,每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子,正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50),表示下面有q次询问。在接下来的q行里,每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时,输入结束。
注意:询问之间无先后关系,都是针对当前状态的!

原题链接:连连看

思路

在给定的地图上搜索通路,因为有方向的限制,在dfs函数参数里需要记录每次搜索的方向和转折次数。因为可能在任意搜索分支上到达终点,为减少到达终点之后多余的搜索,用全局变量isEnd来判断是否已经结束搜索。此外,对于起点到终点的路径被堵的情况,需要在整个dfs流程结束后才能判断是否可行,故用全局变量isSucc来记录结果。为了防止绕圈死循环,需要一个vis数组来记录走过的地方,而bfs的解法需要记录每个位置的搜索方向,不能一个方向搜索过就标记该位置已走过。
特别注意,x是行数y是列数,xy不是通常的坐标系

剪枝:

  1. 转折次数大于2
  2. 不是通路的位置(不为0的地方)
  3. 已转折两次时与目标不在同一直线(其实这里可以剪掉不同向的情况,但是判断条件有点长)
  4. 越界或已走过

另外,有些数据的起点和终点可能 越界、为0、不匹配,这些情况可以在进入dfs函数前直接剪掉。

AC代码

109ms 9600K

#include <cstdio>

const int M = 1002;

int n, m, q;
int map[M][M];
int vis[M][M];

int sx, sy, ex, ey;
//startx starty endx endy

int d[4][2] = {{0, 1}, {-1, 0}, {1, 0}, {0, -1}};
//              右       上       下       左
//              0        1        2        3

bool isEnd, isSucc;

void reset(int (*arr)[M])
{
    for (int i = 0; i < M; ++i)
        for (int j = 0; j < M; ++j)
            arr[i][j] = 0;
}

void dfs(int x, int y, int di, int turn)
{
    if (x == ex && y == ey && turn <= 2)
    {
        isEnd = isSucc = true;
        return;
    }
    //剪掉 转弯次数大于2、不是0的位置、转弯两次时依旧不在同一直线 的情况
    if (turn > 2 || (map[x][y] != 0 && !(x == sx && y == sy)) || (turn == 2 && (ex - x != 0) && (ey - y != 0)) || isEnd)
        return;

    for (int i = 0; i < 4; ++i)
    {
        int tx = x + d[i][0];
        int ty = y + d[i][1];

        //越界或已走过 剪掉
        if (tx < 0 || ty < 0 || tx >= n || ty >= m || vis[tx][ty])
            continue;

        vis[tx][ty] = 1;
        //di为-1代表刚开始,di为i说明没转弯,否则转弯次数+1
        dfs(tx, ty, i, (di == -1 || di == i) ? turn : turn + 1);
        vis[tx][ty] = 0;
    }
}

int main()
{
    //freopen("in.txt", "r", stdin);
    while (scanf("%d%d", &n, &m) != EOF)
    {
        if (n == 0 && m == 0)
            break;
        reset(map);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                scanf("%d", &map[i][j]);
        scanf("%d", &q);
        while (q--)
        {
            reset(vis);
            isSucc = isEnd = false;
            scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
            //地图下标从0开始,故自减
            --sx, --sy, --ex, --ey;
            //起点或终点越界、起点终点重合、起点或终点为0、起点终点不匹配 的条件不进入dfs
            if ((sx >= 0 && sy >= 0 && ex >= 0 && ey >= 0 && sx < n && ex < n && sy < m && ey < m) && (sx != ex || sy != ey) && map[sx][sy] != 0 && map[ex][ey] != 0 && map[sx][sy] == map[ex][ey])
            {
                vis[sx][sy] = 1;
                dfs(sx, sy, -1, 0);
            }

            if (isSucc)
                printf("YES\n");
            else
                printf("NO\n");
        }
    }

    return 0;
}

扩展

非搜索做法

分享到