分析:一个n*m的矩阵,每个格子有12个状态,每次按一次,每个格子转90度,所以整个矩阵只有4种状态,然后爆搜就好了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <queue>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e3+;
struct Node{
int t,x,y;
};
queue<Node>q;
char c[N][N];
int s[][N][N],n,m;
char p[]="0+-|^><vLRUD*";
int a[]={,,,,,,,,,,,,};
int b[]={,,,,,,,,,,,,};
int dp[][N][N];
bool judgel(int x){
if(x==||x==||x==||x==||x==||x==)
return true;
return false;
}
bool judger(int x){
if(x==||x==||x==||x==||x==||x==)
return true;
return false;
}
bool judgeu(int x){
if(x==||x==||x==||x==||x==||x==)
return true;
return false;
}
bool judged(int x){
if(x==||x==||x==||x==||x==||x==)
return true;
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)
scanf("%s",c[i]+);
for(int i=;i<=n;++i)
{
for(int j=;j<=m;++j)
{
for(int k=;k<=;++k)
if(c[i][j]==p[k])
{
s[][i][j]=a[k];
break;
}
}
}
for(int k=;k<=;++k)
{
for(int i=;i<=n;++i)
{
for(int j=;j<=m;++j)
{
s[k][i][j]=b[s[k-][i][j]];
}
}
}
Node st,aim;
scanf("%d%d%d%d",&st.x,&st.y,&aim.x,&aim.y);
memset(dp,-,sizeof(dp));
st.t=;
q.push(st);dp[][st.x][st.y]=;
int ans=INF;
while(!q.empty()){
Node u=q.front();
q.pop();
if(u.x==aim.x&&u.y==aim.y){
break;
}
Node e=u;e.t=(e.t+)%;
if(dp[e.t][e.x][e.y]==-){
dp[e.t][e.x][e.y]=dp[u.t][e.x][e.y]+;
q.push(e);
}
if(u.y>&&judgel(s[u.t][u.x][u.y])&&judger(s[u.t][u.x][u.y-])){
if(dp[u.t][u.x][u.y-]==-){
e=u;--e.y;
dp[e.t][e.x][e.y]=dp[u.t][u.x][u.y]+;
q.push(e);
}
}
if(u.y<m&&judger(s[u.t][u.x][u.y])&&judgel(s[u.t][u.x][u.y+])){
if(dp[u.t][u.x][u.y+]==-){
e=u;++e.y;
dp[e.t][e.x][e.y]=dp[u.t][u.x][u.y]+;
q.push(e);
}
}
if(u.x>&&judgeu(s[u.t][u.x][u.y])&&judged(s[u.t][u.x-][u.y])){
if(dp[u.t][u.x-][u.y]==-){
e=u;--e.x;
dp[e.t][e.x][e.y]=dp[u.t][u.x][u.y]+;
q.push(e);
}
}
if(u.x<n&&judged(s[u.t][u.x][u.y])&&judgeu(s[u.t][u.x+][u.y])){
if(dp[u.t][u.x+][u.y]==-){
e=u;++e.x;
dp[e.t][e.x][e.y]=dp[u.t][u.x][u.y]+;
q.push(e);
}
}
}
for(int i=;i<;++i)
if(dp[i][aim.x][aim.y]!=-){
ans=min(dp[i][aim.x][aim.y],ans);
}
if(ans==INF)ans=-;
printf("%d\n",ans);
return ;
}

最新文章

  1. Win7 安装SQL SERVER 2012需要SP1补丁
  2. 获取FIle路径下所有文件的地址和名称
  3. sql-insert一条语句执行多条数据插入
  4. Maven的作用总结
  5. 【MySQL】结构行长度的一些限制
  6. sysbench压力测试工具简介和使用(一)
  7. 作死遇到的坑--view向下偏移
  8. [ASP.NET] 下一代ASP.NET开发规范:OWIN
  9. *.bz2和*.gz分别是什么压缩格式
  10. nginx 代理服务器 502错误
  11. HW5.11
  12. c语言开源项目--SQLite学习资料总结
  13. JQ第一篇
  14. C# Best Practices - Creating Good Methods
  15. PHP使用正则表达式验证电话号码(手机和固定电话)
  16. mnesia
  17. Myeclipse 配置多个tomcat
  18. mysql 计算两个日期之间的工作日天数
  19. QoS 服务质量
  20. 【VI】如何删除匹配指定字符串的行(已解决)

热门文章

  1. 然爸读书笔记(2014-10)----Bootsrap用户手册
  2. JPA2 关于 PagingAndSortingRepository
  3. Visual Studio 2013 之 Productivity Power Tools
  4. TCP/IP长连接和短连接
  5. http://blog.csdn.net/itplus/article/details/10088625
  6. c++ 小片段
  7. UNITY3D使用NGUI制作自适应UI的总结
  8. Android支付接入(二):移动游戏基地
  9. pthread_create用法
  10. Oracle sql查询