首页 > 代码库 > hdu 1175 连连看

hdu 1175 连连看

    注意事项:

    (1)只有数字相同的两个点可以相互消除

    (2)转折次数不能超过两次

    (3)数字都为‘0’, ‘0’的不能消除

    (4)两个坐标不能相同

  

    解题思路:

    

//第一组数据
3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4

   从开始的点判断下一步走四个方向中哪些方向是可以走的,可以走的条件是下一步为空(即‘0’),并且按这种方法走下一步可以使拐弯次数减少

   在这里将开始的点s,的方向初始化为-1,拐弯次数为-1,其他点的拐弯次数初始化为10

  

      

        绿色箭头反向为不可以行走的方向,因为如果走的是绿色箭头这一方向,已经走过一次,要是又走这一方向,不会使拐弯次数减少


#include <iostream>
#include <queue>
using namespace std;
#define MAX 1005
struct Node
{
	int x, y, num, dir;//拐弯次数,方向
	friend bool operator < (Node a, Node b)
	{
           return a.num > b.num;//拐弯次数少的点优先考虑
	}
};
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int v[MAX][MAX], g[MAX][MAX];
Node s, e;
Node tmp;//记录拐点
int x, y;
void Clear()
{
	int i, j;
	for (i=1; i<=x; i++)
	  for (j=1; j<=y; j++)
	    v[i][j] = 10;
}
int main()
{
    int i, j, num;
	Node p, tmp;
	while (cin>>x>>y && (x||y))
	{
	    memset(g, -1, sizeof(g));
	    for (i=1; i<=x; i++)
	      for (j=1; j<=y; j++)
		cin>>g[i][j];
	    cin>>num;
	    while (num--)
	   {
	      cin>>s.x>>s.y>>e.x>>e.y;
	      if (g[s.x][s.y]!=g[e.x][e.y] || g[s.x][s.y]==0 ||(s.x==e.x&&s.y==e.y))
		   cout<<"NO"<<endl;
	      else
	      { 
		 Clear();
		 int flag = 0;
		 priority_queue<Node>q;
		 s.num = s.dir = -1;
		 v[s.x][s.y] = -1;
		 q.push(s);
		 while (!q.empty())
		{
		   tmp = q.top();
		   q.pop();
		   if (tmp.num==3)
			break;
		   if (tmp.x==e.x&&tmp.y==e.y)
		   {
			cout<<"YES"<<endl;
			flag = 1;
			break;
		   }
		  for (i=0; i<4; i++)
		  {
			p.x = tmp.x + dx[i];
			p.y = tmp.y + dy[i];
			if (g[p.x][p.y]==0||(p.x==e.x && p.y==e.y))
			{
			     if (i!=tmp.dir)
			         p.num = tmp.num + 1;
			     else
				 p.num = tmp.num;
			     p.dir = i;
			     if (p.num<v[p.x][p.y])
		            {
				v[p.x][p.y] = p.num;
				q.push(p);
			    }
			}
		  }
		}
		if(flag==0)
                   cout<<"NO"<<endl;
	    }
	 }
      }
	return 0;
}