题目:VJ
思路:
BFS+回溯,但是要剪枝,看了dalao的题解,超时+WA无数发,终于过了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<queue>
#include<cmath>
//#include<map>
#include<string>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
const int N=300;
using namespace std;
char map[N][N];
char dir[N][N];
int vis[N][N],fx[N][N],fy[N][N];
int n,m,sx,sy,ex,ey,to[4][2]={1,0,-1,0,0,1,0,-1};
char turn[4]={'d','u','r','l'};
struct node{
int x,y;
int step;
int i;
};
queue<node> q;
void init(){
memset (vis,-1,sizeof(vis));
while(!q.empty()) q.pop();
}
int judge(int x,int y,int step){
if(x>=1 && x<=n && y>=1 && y<=m && map[x][y]!='#' && (vis[x][y]==-1 || vis[x][y]==step)) return 1;
return 0;
}
void add(int x,int y,int i,int step){
node a;
x+=to[i][0];
y+=to[i][1];
while(judge(x,y,step)){
if(vis[x][y]!=step){
dir[x][y]=turn[i];
vis[x][y]=step;
fx[x][y]=x-to[i][0];
fy[x][y]=y-to[i][1];
a.i=i;
a.x=x;
a.y=y;
a.step=step;
q.push(a);
}
x+=to[i][0];
y+=to[i][1];
}
}
void paint(int i){
int x,y,tx,ty;
tx=fx[ex][ey];
ty=fy[ex][ey];
x=ex;
y=ey;
while(tx!=sx || ty!=sy){
char wh=dir[tx][ty];
char go=dir[x][y];
if(wh!=go){
if(wh=='u'){
if(go=='l'){
map[tx][ty]='\\';
}
else if(go=='r'){
map[tx][ty]='/';
}
}
else if(wh=='d'){
if(go=='r'){
map[tx][ty]='\\';
}
else if(go=='l'){
map[tx][ty]='/';
}
}
else if(wh=='l'){
if(go=='u'){
map[tx][ty]='\\';
}
else if(go=='d'){
map[tx][ty]='/';
}
}
else if(wh=='r'){
if(go=='d'){
map[tx][ty]='\\';
}
else if(go=='u'){
map[tx][ty]='/';
}
}
}
x=tx;
y=ty;
tx=fx[x][y];
ty=fy[x][y];
}
}
void bfs(int dd){
int x,y;
init();
node a,b;
vis[sx][sy]=100000;
dir[sx][sy]='o';
add(sx,sy,dd,0);
while(!q.empty()){
a=q.front();
q.pop();
if(a.x==ex && a.y==ey){
paint(a.i);
return;
}
b.step=a.step+1;
for(int i=0;i<4;i++){
b.x=a.x+to[i][0];
b.y=a.y+to[i][1];
if(judge(b.x,b.y,b.step)){
add(a.x,a.y,i,b.step);
}
}
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",map[i]+1);
for(int j=1;j<=m;j++){
if(map[i][j]=='C'){
ex=i;ey=j;
}
else if(map[i][j]=='<' || map[i][j]=='>' || map[i][j]=='v' || map[i][j]=='^'){
sx=i;sy=j;
}
}
}
//to[4][2]={1,0, -1,0, 0,1, 0,-1}
int direction;
if(map[sx][sy]=='<') direction=3;
else if(map[sx][sy]=='>') direction=2;
else if(map[sx][sy]=='^') direction=1;
else direction=0;
bfs(direction);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%c",map[i][j]);
}
printf("\n");
}
}
return 0;
}
SPOJ LAS(BFS)题解的更多相关文章
-
DFS与BFS题解:[kaungbin]带你飞 简单搜索 解题报告
DFS and BFS 在解题前我们还是大致讲一下dfs与bfs的.(我感觉我不会bfs) 1.DFS dfs(深度优先算法) 正如其名,dfs是相当的深度,不走到最深处绝不回头的那种. 深度优先搜 ...
-
C++版 - 剑指offer 面试题23:从上往下打印二叉树(二叉树的层次遍历BFS) 题解
剑指offer 面试题23:从上往下打印二叉树 参与人数:4853 时间限制:1秒 空间限制:32768K 提交网址: http://www.nowcoder.com/practice/7fe2 ...
-
畅通工程(自己写的BFS,但后面想了下并查集更好更快)
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省*“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可). ...
-
AcWing:177. 噩梦(bfs)
给定一张N*M的地图,地图中有1个男孩,1个女孩和2个鬼. 字符“.”表示道路,字符“X”表示墙,字符“M”表示男孩的位置,字符“G”表示女孩的位置,字符“Z”表示鬼的位置. 男孩每秒可以移动3个单位 ...
-
HDU 1560 DNA sequence (IDA* 迭代加深 搜索)
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1560 BFS题解:http://www.cnblogs.com/crazyapple/p/321810 ...
-
洛谷P1605走迷宫
传送 这是一道dfs,但是...但是....但是它竟然被放在bfs练习题辣!!!! 打了半天bfs,发现路径不会标记了,于是发现好像有什么不对的,似乎dfs要简单一点,于是半路跑去打dfs,结果打了半 ...
-
记 2020蓝桥杯校内预选赛(JAVA组) 赛后总结
目录 引言 结果填空 1. 签到题 2. 概念题 3. 签到题 4. 签到题 程序题 5. 递增三元组[遍历] 6. 小明的hello[循环] 7. 数位递增[数位dp] 8. 小明家的草地[bfs] ...
-
“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&;&;源码【A,水,B,水,C,水,D,快速幂,E,优先队列,F,暴力,G,贪心+排序,H,STL乱搞,I,尼姆博弈,J,差分dp,K,二分+排序,L,矩阵快速幂,M,线段树区间更新+Lazy思想,N,超级快速幂+扩展欧里几德,O,BFS】
黑白图像直方图 发布时间: 2017年7月9日 18:30 最后更新: 2017年7月10日 21:08 时间限制: 1000ms 内存限制: 128M 描述 在一个矩形的灰度图像上,每个 ...
-
HDU1043 Eight(八数码:逆向BFS打表+康托展开)题解
Eight Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Sub ...
随机推荐
-
nginx for linux安装及安装错误解决
nginx:下载地址:http://www.nginx.org/ 1.GCC编译器 安装指令 :yum install -y gcc 如果你所使用的是ubuntu,则安装指令为:apt-get i ...
-
NBUT 1673 迷宫问题(DP)
[1673] 迷宫问题 时间限制: 1000 ms 内存限制: 65535 K 问题描述 Alex的猫咪不小心走进了迷宫,Alex为了心爱的猫咪,决定进入迷宫去解救他的猫咪. 已知猫咪坐标为(n - ...
-
WordPress Design Approval System插件‘step’参数跨站脚本漏洞
漏洞名称: WordPress Design Approval System插件‘step’参数跨站脚本漏洞 CNNVD编号: CNNVD-201309-084 发布时间: 2013-09-11 更新 ...
-
mysq开启慢查询
1 将未建立索引的sql放到慢查询日志中 查看 log_queries_not_using_indexes 是否为on show variables like 'log%'; 将 log_querie ...
-
H5 input输入限制最大位数,和调用小键盘需求发生冲突的解决办法
首先,限制输入最大位数时,input有自带的属性maxlength. <input type="text" name="email" maxlength= ...
-
Node笔记五-进程、线程
进程 -每一个正在运行的应用程序都称之为进程 -每一个应用程序都至少有一个进程 -进程是用来给应用程序提供一个运行的环境 -进程是操作系统为应用程序分配资源的一个单位线程 -用来执行应用程序中的代码 ...
-
简单数论之整除&;质因数分解&;唯一分解定理
[整除] 若a被b整除,即a是b的倍数,那么记作b|a("|"是整除符号),读作"b整除a"或"a能被b整除".b叫做a的约数(或因数),a ...
-
C#字符串转二进制、二进制转字符串
最近公司要做一个操作日志的模块,如果将操作日志以字符串的形式存到后台数据库,非常浪费内存,不可取,特意写了字符串与二进制相互转换的函数. 1.字符串转二进制 private string String ...
-
Tesseract 引擎翻译
Tesseract 引擎翻译 Category: 图像识别 Last Edited: Sep 17, 2018 10:29 AM Tags: tesseract,字符识别,翻译 1.英文原文(中文翻译 ...
-
如何使不同时区的时间与京8区一致?(JS实现)
如何使不同时区的时间与京8区一致?(JS实现) Update:2019/1/28 更简单的是使用这个函数(toDate): // 自定义日期格式如下(年月日都必须提供): // "2011- ...