题目:http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5501

思路:DFS,用了递归就溢出,所以可能得用非递归的。把所有可能到达终点的可能路径都计算,最后比较找最佳。限制条件很多,要细打细算。很烦,不想改了再试,写了很久了

 #include <iostream>
#include <cstdio>
#include <string>
#include <map>
#include <deque>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
char dun[][];
bool vis[][];
struct node
{
int x,y;
int peln,path; //惩罚/ 第几层
int s[]; //遇到的陷阱,26开始就是A
};
stack<node> que;
deque<node> anslist; int stax, stay;
int tarx, tary;
int n, m;
int fat, mins; void init(node &tmp) //初始化怪物标记s
{
for(int i=; i<; i++)
tmp.s[i]='';
}
bool tar(node tmp) //判断是否是目的地
{
if( tmp.x==tarx && tmp.y==tary )
return true;
else
return false;
}
bool cango(node tmp) //判断能不能走
{
if(tmp.x>=&&tmp.x<n&&tmp.y>=&&tmp.y<m )
{
if( dun[tmp.x][tmp.y]=='#' )
return false;
else
return true;
}
else
return false;
}
void adj_mon(node &tmp) //计算怪物惩罚
{
char c1='',c2='',c3='',c4='', c5=''; //走过可能干掉3只怪物 if( isupper( dun[tmp.x][tmp.y] ) ) //是怪物
{
c1=dun[tmp.x][tmp.y];
} node node1=tmp;
node1.x-=;
if( cango(node1)&&isupper( dun[tmp.x-][tmp.y] ) ) //是怪物
{
c2=dun[tmp.x-][tmp.y];
//cout<<"begin"<<endl;
} node1=tmp;
node1.x+=;
if( cango(node1)&&isupper( dun[tmp.x+][tmp.y] ) ) //是怪物
{
c3=dun[tmp.x+][tmp.y];
//cout<<"begin"<<endl;
} node1=tmp;
node1.y+=;
if( cango(node1)&&isupper( dun[tmp.x][tmp.y+] ) ) //是怪物
{
c3=dun[tmp.x][tmp.y+];
//cout<<"begin"<<endl;
} node1=tmp;
node1.y-=;
if( cango(node1)&&isupper( dun[tmp.x][tmp.y-] ) ) //是怪物
{
//cout<<"begin"<<endl;
c5=dun[tmp.x][tmp.y-];
} //*************************************
if(c1!=''&&tmp.s[ c1-'A'+ ]=='')
{
tmp.s[ c1-'A'+ ]=true;
tmp.peln+=( c1-'A'+ );
//cout<<"begin"<<endl;
} if(c2!=''&&tmp.s[ c2-'A'+ ]=='')
{
tmp.s[ c2-'A'+ ]=true;
tmp.peln+=( c2-'A'+ );
//cout<<"begin"<<endl;
} if(c3!=''&&tmp.s[ c3-'A'+ ]=='')
{
tmp.s[ c3-'A'+ ]=true;
tmp.peln+=(c3-'A'+);
//cout<<"begin"<<endl;
} if(c4!=''&&tmp.s[ c4-'A'+ ]=='')
{
tmp.s[ c4-'A'+ ]=true;
tmp.peln+=(c4-'A'+);
//cout<<"begin"<<endl;
} if(c5!=''&&tmp.s[ c5-'A'+ ]=='')
{
tmp.s[ c5-'A'+ ]=true;
tmp.peln+= c5-'A'+;
//cout<<"begin"<<endl;
} }
void trap(node &tmp) //计算陷阱惩罚
{
if( islower(dun[tmp.x][tmp.y]) ) //陷阱
tmp.peln += (dun[tmp.x][tmp.y] - 'a'+);
}
void cal_pel(node &tmp) //计算惩罚
{
trap(tmp);
adj_mon(tmp);
} int bfs(node tmp)
{
//判断四周有没有能进盏的
node node1=tmp;
node1.x-=;
if(cango(node1)) //合法
{ cal_pel(node1);
node1.path++;
if(tar(node1))
anslist.push_back(node1);
else if(vis[node1.x][node1.y]==false) //非目的
{
que.push(node1);
vis[node1.x][node1.y]=true;
bfs(node1);
que.pop();
vis[node1.x][node1.y]=false; } } node1=tmp;
node1.x+=;
if(cango(node1)) //合法
{
cal_pel(node1); node1.path++;
if(tar(node1))
anslist.push_back(node1);
else if(vis[node1.x][node1.y]==false) //非目的
{
que.push(node1);
vis[node1.x][node1.y]=true;
bfs(node1) ;
que.pop();
vis[node1.x][node1.y]=false;
}
} node1=tmp;
node1.y-=;
if(cango(node1)) //合法
{
cal_pel(node1); node1.path++;
if(tar(node1))
anslist.push_back(node1);
else if(vis[node1.x][node1.y]==false) //非目的
{
que.push(node1);
vis[node1.x][node1.y]=true;
bfs(node1) ;
que.pop();
vis[node1.x][node1.y]=false;
}
} node1=tmp;
node1.y+=;
if(cango(node1)) //合法
{
cal_pel(node1); node1.path++;
if(tar(node1))
anslist.push_back(node1);
else if(vis[node1.x][node1.y]==false) //非目的
{
que.push(node1);
vis[node1.x][node1.y]=true;
bfs(node1) ;
que.pop();
vis[node1.x][node1.y]=false;
} }
return ;
} int main()
{
//freopen("input.txt", "r", stdin);
int t;
cin>>t;
while(t--)
{
anslist.clear();
memset(dun, , sizeof(dun));
memset(vis, , sizeof(vis)); cin>>n>>m;
cin>>stax>>stay>>tarx>>tary;
stax-=;stay-=;tarx-=;tary-=; for(int i=; i<n; i++)
for(int j=; j<m; j++)
cin>>dun[i][j]; node tmp;
init(tmp);
tmp.x=stax; tmp.y=stay; tmp.peln=; tmp.path=; //起点
vis[tmp.x][tmp.y]=true;
que.push(tmp); //先进队
bfs(que.top()); deque<node>::iterator it=anslist.begin();
int min_path=;
int min_pel=;
for( ; it!=anslist.end(); it++)
{
//cout<<it->peln<<" "<<it->path<<endl; if(it->peln<=min_pel&&it->path<=min_path)
{
min_pel=it->peln;
min_path=it->path;
} }
cout<<min_pel<<" "<<min_path<<endl; } return ;
}

递归式的,seg错

最新文章

  1. 虚拟机:Python虚拟机的基本了解
  2. Oracle登录时提示错误,导致用户无法登录
  3. 关键字 static
  4. uva 624
  5. img标签块状与内联的博弈
  6. Linux中TCP wrapper的使用
  7. 深度学习实践系列(1)- 从零搭建notMNIST逻辑回归模型
  8. 为什么Java 两个Integer 中1000==1000为false而100==100为true?
  9. Servlet 笔记-异常处理
  10. Linux SHELL中sh和bash的区别
  11. ios自动打包-fastlane 安装、使用、更新和卸载
  12. Logstash - Working with plugins(使用插件)
  13. c#+.net常用功能点
  14. PHP 简单学习(“hello world”,变量,运算符)
  15. Django内置权限扩展案例
  16. unity执行顺序问题(如何再次执行start方法)
  17. TCDB 数据库简介
  18. Nginx访问控制_IP访问控制(http_access_module)原理、局限性、解决方法讲解
  19. js 实现商品放大镜效果
  20. 两台电脑在不同情况下ping的情况

热门文章

  1. Linux的.run文件简单制作
  2. Multi-task Pose-Invariant Face Recognition 论文笔记
  3. win10外接显示器时有些应用和里面的字体显示比较模糊
  4. Educational Codeforces Round 52F(树形DP,VECTOR)
  5. 51nod1010(枚举+二分)
  6. LCA 【bzoj1787】[Ahoi2008]Meet 紧急集合
  7. css3旋转立方体-_-
  8. springMVC form表单提交多个对象集合--使用ajax提交--前台json格式数据封装方法
  9. maven插件: shade, assembly
  10. 【ACM】拦截导弹 - 0-1背包问题