首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。