题意

给出n* n 的图,A为起点,B为终点,* 为障碍,.可以行走,问最少需要拐90度的弯多少次,无法到达输出-1。

解析

思路:构造N * M * 4个点,即将原图的每个点分裂成4个点。其中点(i,j,k)表示在(i,j)时人的方向是k,然后对于两个点(i,j,k)和(i,j,kk),如果k和kk是两个旋转90度能转换的方向,就连一条边权为1的边,而对于(i,j,k)和(i+dx[ k],j+dy[k],k)连一条边权为0的边,表示从(i,j)在方向为k的情况下能向k方向走一步到达(i+dx[k],j+dy[k],k)。因为起始和终止的方向不确定,故再添加一个源点和一个汇点,源点向起始位置四个方向连边权为0的边,汇点向终止位置四个方向连边权为0的边,然后求源点到汇点的最短路即可。

爆搜代码

#include<bits/stdc++.h>
using namespace std;
int n,sx,sy,ex,ey,a[110][110];
char k;
bool book[110][110];
int ans=1<<30;
bool cheak(int x,int y){
if(x<1||y>n||y<1||x>n||a[x][y]||book[x][y]) return false;
else return true;
}
void dfs(int x,int y,int dir,int step){
if(x==ex&&y==ey){
ans=min(step,ans);
return;
}
if(step>ans) return;
if(dir){
if(cheak(x+1,y)){
book[x+1][y]=1;
dfs(x+1,y,dir,step);
book[x+1][y]=0;
}
if(cheak(x-1,y)){
book[x-1][y]=1;
dfs(x-1,y,dir,step);
book[x-1][y]=0;
}
if(cheak(x,y+1)){
book[x][y+1]=1;
dfs(x,y+1,0,step+1);
book[x][y+1]=0;
}
if(cheak(x,y-1)){
book[x][y-1]=1;
dfs(x,y-1,0,step+1);
book[x][y-1]=0;
}
}
else{
if(cheak(x+1,y)){
book[x+1][y]=1;
dfs(x+1,y,1,step+1);
book[x+1][y]=0;
}
if(cheak(x-1,y)){
book[x-1][y]=1;
dfs(x-1,y,1,step+1);
book[x-1][y]=0;
}
if(cheak(x,y+1)){
book[x][y+1]=1;
dfs(x,y+1,dir,step);
book[x][y+1]=0;
}
if(cheak(x,y-1)){
book[x][y-1]=1;
dfs(x,y-1,0,step);
book[x][y-1]=0;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
scanf("%c",&k);
if(k=='A'){
sx=i;
sy=j;
}
else if(k=='B'){
ex=i;
ey=j;
}
else if(k=='x'){
a[i][j]=1;
}
else if(k=='.'){
a[i][j]=0;
}
else j--;
}
}
dfs(sx,sy,0,0);
dfs(sx,sy,1,0);
if(ans==1<<30) printf("-1");
else printf("%d",ans);
return 0;
}

最新文章

  1. BZOJ 1044 木棍分割 解题报告(二分+DP)
  2. jquery鼠标右键事件
  3. 每天一个linux命令(19):find 命令概览
  4. tableView使用的易忘技术点(相对于自己)
  5. poj 3026 bfs+prim Borg Maze
  6. [转帖]Speed-BI数据分析案例:2016年8月汽车销量排行榜
  7. ExtJS4.2.1自定义主题(theme)样式详解
  8. DLLImport
  9. swfit-小知识Demo
  10. MATLAB批量读入图片
  11. 【shell脚本练习】grep sed awk
  12. centos 添加右键在终端打开
  13. 51nod 1238 最小公倍数之和 V3
  14. Java中的CAS实现原理
  15. VC++6 调用teststand api的方法
  16. 使用block的好处
  17. vue v-for 和 v-if 、v-else一起使用造成的bug
  18. SSH整合:Unable to instantiate Action, employeeAction, defined for &#39;emp-list&#39; in namespace &#39;/&#39;employeeAction - action
  19. Week4-作业1
  20. PL/SQL编程基础(一):PL/SQL语法简介(匿名PL/SQL块)

热门文章

  1. Flink 从0到1学习 —— Flink 中如何管理配置?
  2. 两份简单的logstash配置
  3. 从JavaScript到Python之异常
  4. Windows 下安装 Python + Django
  5. 线性分类 Linear Classification
  6. java的八种数据类型
  7. 有关element 的一些问题(随时更新)
  8. MySQL学习随笔记录
  9. Source Maps简介
  10. 右键新建 .md