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