hdu1175 连连看 --DFS/BFS

原题链接： ​​ http://acm.hdu.edu.cn/showproblem.php?pid=1175​​

直接上代码，不是很难。

#define _CRT_SECURE_NO_DEPRECATE 
#define _CRT_SECURE_Cy1_OVERLOAD_STANDARD_NAMES 1 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int visited[1005][1005];
int a[1005][1005];
int n, m;
int x1, y1;
int x2, y2;
bool flag;

/* x,y坐标，z朝向(1:up,2:down,3:left,4right)，k转弯次数 */
void DFS(int x, int y, int z, int k)
{
  if (flag)
    return;
  if (k >= 3)//转弯超过两次，不行
    return;
  if (x <= 0 || y <= 0 || x > n || y > m)//越界
    return;
  if (x == x2&y == y2)//找到
  {
    flag = true;
    return;
  }
  if (k == 2)//剪枝，转弯两次时，看目的点的坐标与现在的朝向是否在一个方向上，不在的话就返回
  {
    if (!(z == 1 && x > x2 && y == y2 || z == 2 && x<x2 && y == y2 || z == 3 && y>y2 && x == x2 || z == 4 && y < y2 && x == x2))
      return;
  }
  if (a[x][y] != 0)
    return;
  if (visited[x][y])
    return;

  visited[x][y] = 1;
  if (z == 1)//上
  {
    DFS(x - 1, y, 1, k);
    DFS(x + 1, y, 2, k + 1);
    DFS(x, y - 1, 3, k + 1);
    DFS(x, y + 1, 4, k + 1);
  }
  else if (z == 2)//下  
  {
    DFS(x - 1, y, 1, k + 1);
    DFS(x + 1, y, 2, k);
    DFS(x, y - 1, 3, k + 1);
    DFS(x, y + 1, 4, k + 1);
  }
  else if (z == 3)//左  
  {
    DFS(x - 1, y, 1, k + 1);
    DFS(x + 1, y, 2, k + 1);
    DFS(x, y - 1, 3, k);
    DFS(x, y + 1, 4, k + 1);
  }
  else if (z == 4)//右  
  {
    DFS(x - 1, y, 1, k + 1);
    DFS(x + 1, y, 2, k + 1);
    DFS(x, y - 1, 3, k + 1);
    DFS(x, y + 1, 4, k);
  }
  visited[x][y] = 0;
}
int main()
{
  while (~scanf("%d%d", &n, &m) && (n || m))
  {
    int i, j;
    int t;

    for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++)
        scanf("%d", &a[i][j]);

    scanf("%d", &t);

    while (t--)
    {
      flag = false;
      memset(visited, 0, sizeof(visited));
      scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

      if ((a[x1][y1] == a[x2][y2]) && a[x1][y1] != 0)
      {
        DFS(x1 - 1, y1, 1, 0);
        DFS(x1 + 1, y1, 2, 0);
        DFS(x1, y1 - 1, 3, 0);
        DFS(x1, y1 + 1, 4, 0);
        if (flag)
          printf("YES\n");
        else
          printf("NO\n");
      }
      else
        printf("NO\n");;
    }
  }

  return 0;
}

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<array>
#include<vector>
#include<queue>
using namespace std;

int n, m;
int q;
int a[1005][1005];
int si, sj, ei, ej;
int dir[4][2] = { 1,0,-1,0,0,-1,0,1 };

struct Node
{
  int i;
  int j;
  int step;
  int dir;
  Node(){}
  Node(int _i,int _j,int _step,int _dir):i(_i),j(_j),step(_step),dir(_dir){}
};

int bfs()
{
  queue<Node> Q;
  for (int i = 0; i < 4; i++)
  {
    int new_i = si + dir[i][0];
    int new_j = sj + dir[i][1];
    if (new_i >= 1 && new_i <= n&&new_j >= 1 && new_j <= m && (a[new_i][new_j] == 0 || (new_i == ei&&new_j == ej)))
      Q.push(Node(new_i, new_j, 0, i + 1));
  }

  while (!Q.empty())
  {
    Node temp = Q.front();
    Q.pop();
    if (temp.step == 2 && temp.i != ei && temp.j !=ej)  //此处的剪枝很重要，不加会超时
      continue;
    if (temp.step > 2)
      continue;
    if (temp.i == ei&&temp.j == ej)
      return 1;
    for (int i = 0; i < 4; i++)
    {
      if (temp.dir == 1 && i + 1 == 2 ||
        temp.dir == 2 && i + 1 == 1 ||
        temp.dir == 3 && i + 1 == 4 ||
        temp.dir == 4 && i + 1 == 3)
        continue;

      int new_i = temp.i + dir[i][0];
      int new_j = temp.j + dir[i][1];
      if (new_i >= 1 && new_i <= n&&new_j >= 1 && new_j <= m && (a[new_i][new_j] == 0 || (new_i == ei&&new_j == ej)))
      {
        if (temp.dir == i + 1)
          Q.push(Node(new_i, new_j, temp.step, i + 1));
        else
          Q.push(Node(new_i, new_j, temp.step + 1, i + 1));
      }
    }
  }
  return -1;
}


int main()
{
  while (~scanf("%d%d", &n, &m) && (n || m))
  {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        scanf("%d", &a[i][j]);
    scanf("%d", &q);
    while (q--)
    {
      scanf("%d%d%d%d", &si, &sj, &ei, &ej);
      if (a[si][sj] != a[ei][ej] || (a[si][sj] == a[ei][ej] && a[si][sj] == 0) || (si == ei&&sj == ej))
        printf("NO\n");
      else
      {
        if (bfs() == 1)
          printf("YES\n");
        else
          printf("NO\n");
      }
    }
  }
  return 0;
}