简单连连看 hdu 1175

此题是一个简单版得连连看，而且只是判断给出的两个坐标所在的图片是否可以相消，而不是给出一个连连看相消的序列。

?

?

简单来说就是广搜，从起始点向4个方向扩展，记录每个点的转折次数，也就是代价了。对于代价小于2的点（转折<=2次）的继续在队列扩展，其他的不用入队列 了。

?

记录一下猥琐的代码：

?

#include <stdio.h>#include <iostream>#define N 1001using namespace std;int g[N][N];int tag[N][N];int cnt[N][N];int que[N*N][2];int dire[4][2] = {{-1,0},{0,1}, {1,0},{0,-1}};int lianliankan(int m, int n, int x1, int y1, int x2, int y2){    int i, j;    int x, y, xx, yy;    int rear=0, front=0;        if ( g[x1][y1] != g[x2][y2] )   // if the targets not equal      return 0;    if ( g[x1][y1] == 0 || g[x2][y2] == 0 )  // if one of the target is empty(that is to say no object in there)       return 0;        for ( i = 0;i < m; ++i )        for ( j = 0; j < n; ++j )            {                cnt[i][j]= 3;                tag[i][j] = -1;            }    for ( i = 0; i < 4; ++i )    {        x = x1 + dire[i][0];        y = y1 + dire[i][1];        if ( x >= 0 && x < m && y >=0 && y < n )        {            if ( x==x2 && y == y2 )               return 1;            if ( g[x][y] )             continue;            tag[x][y] = i;            cnt[x][y] = 0;            que[front][0] = x;            que[front++][1] = y;        }     }        cnt[x1][y1] = 0;    while ( rear < front )    {        xx = que[rear][0];        yy = que[rear][1];        for ( i = 0; i < 4 ; ++i )        {            x = xx + dire[i][0];            y = yy + dire[i][1];            if ( x >= 0 && x < m && y >= 0 && y < n )            {                     if ( i == tag[xx][yy] && cnt[x][y] > cnt[xx][yy]) // line                    {                       if ( x == x2 && y == y2 )                          return 1;                       if ( g[x][y] )                          continue;                       tag[x][y] = i;                       cnt[x][y] = cnt[xx][yy];                       que[front][0] = x;                       que[front++][1] = y;                                           }                    else if ( i != tag[xx][yy] && cnt[x][y] > cnt[xx][yy] + 1 )  // broken line                    {                        if ( x == x2 && y == y2 )                          return 1;                        if ( g[x][y] )                           continue;                        tag[x][y] = i;                        cnt[x][y] = cnt[xx][yy] + 1;                        que[front][0] = x;                        que[front++][1] = y;                                            }            }        }        rear++;    }    return 0;}int main(){    int m, n;    int i, j, k;    int x1, y1, x2, y2;    while( scanf("%d%d", &m, &n) != EOF &&(m && n) )    {           for ( i = 0; i < m; ++i )               for ( j = 0; j < n; ++j )                   scanf("%d", &g[i][j]);           int q;           scanf("%d", &q);           for ( i = 0;i < q; ++i )           {               scanf("%d%d%d%d", &x1, &y1, &x2, &y2);                           if ( lianliankan(m,n,x1-1,y1-1,x2-1,y2-1) )                  printf("YES\n");               else                   printf("NO\n");                          }           }            return 0;}

?

?

?