处理连连看问题。

要求拐弯方向不多于两次。剪枝很重要!!!

用dir记录当前方向。Orz,居然没想到。

 #include<iostream>
#include<cstring>
#include<algorithm>
#define maxn 1005
using namespace std;
const int dx[]={-,,,},dy[]={,,-,};
int map[maxn][maxn],V[maxn][maxn];
int n,m,flag,x1,x2,y1,y2;
void dfs(int x,int y,int num,int dir){
if (flag || x< || x>=n || y< || y>=m || V[x][y]) return ;
if (num== && x!=x2 && y!=y2) return ;//当拐弯数为2,但与终点不在同一方向
if (num>) return ;
if (num<= && x==x2 && y==y2){
flag=;
return ;
}
if (map[x][y]!=){
if (x==x1 && y==y1) ;
else return ;
}//当前不为零且不为起点,即路径上有棋子
V[x][y]=;
for (int i=;i<;i++){
int xx=x+dx[i],yy=y+dy[i];
if (i==dir) dfs(xx,yy,num,i);
else dfs(xx,yy,num+,i);
}
V[x][y]=;
return ;
}
int main(){
int t;
while (cin >> n >> m && n+m){
memset(map,,sizeof(map));
for (int i=;i<n;i++){
for (int j=;j<m;j++){
cin >> map[i][j];
}
}
cin >> t;
while (t--){
cin >> x1 >> y1 >> x2 >> y2;
x1--,y1--,x2--,y2--;
if (x1==x2 && y1==y2){
cout << "NO\n";
continue;
}//起点与终点相同不能消去
if (map[x1][y1]!=map[x2][y2] || !map[x1][y1] || !map[x2][y2]){
cout << "NO\n";
continue;
}//起点与终点不同,或起点或终点位置没有棋子
if (x1< || x1>=n || y1< || y1>=m || x2< || x2>=n || y2< || y2>=m){
cout << "NO\n";
continue;
}//所给坐标超出当前范围
flag=;
memset(V,,sizeof(V));
for (int i=;i<n;i++){
dfs(x1+dx[i],y1+dy[i],,i); //从一个点的四个方向开始 ,拐弯数 ,当前方向
}
if (flag) cout << "YES\n";
else cout << "NO\n";
}
}
return ;
}

最新文章

  1. 【算法与数据结构】二叉搜索树的Java实现
  2. [Leetcode] Merge Intevals
  3. link,unlink,remove, rename函数
  4. sql 语句查询练习题
  5. Hibernate各种主键生成策略与配置详解《转》
  6. 51nod 1021 石子归并(dp)
  7. opencv 在工业中的应用:圆孔定位
  8. &lt;转&gt;SQL的执行顺序
  9. RabbitMQ系列教程之七:RabbitMQ的 C# 客户端 API 的简介
  10. 组合模式(Composite)
  11. Caused by: java.lang.ClassNotFoundException: flex.messaging.io.BeanProxy
  12. 在网页中使用particlesjs实现背景的动态粒子特效
  13. Python爬虫开发与项目实战
  14. nuxt.js实战之引入jquery
  15. 列出cron的下几次运行时间
  16. 从入门到深入FIDDLER 2
  17. 01: docker 基本使用
  18. 《高性能MySQL》学习笔记
  19. 机器学习理论基础学习9--- EM 算法
  20. [leetcode]163. Missing Ranges缺失范围

热门文章

  1. Java8 改进的匿名内部类:
  2. geoserver 源码介绍
  3. Photoshop中比较实用的小技巧
  4. 并发编程(二)concurrent 工具类
  5. ListView单行刷新
  6. 笔记本的Windows系统怎么设置有了外接鼠标后停用触摸板
  7. Matlab 中以分数显示结果
  8. python-optparse模块给脚本增加参数选项
  9. Content-Type,内容类型
  10. (并查集 建立关系)食物链 -- POJ-- 1182