SPOJ LAS(BFS)题解

时间:2021-10-13 12:58:27

题目: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)题解的更多相关文章

  1. DFS与BFS题解:&lbrack;kaungbin&rsqb;带你飞 简单搜索 解题报告

    DFS and  BFS 在解题前我们还是大致讲一下dfs与bfs的.(我感觉我不会bfs) 1.DFS dfs(深度优先算法) 正如其名,dfs是相当的深度,不走到最深处绝不回头的那种. 深度优先搜 ...

  2. C&plus;&plus;版 - 剑指offer 面试题23:从上往下打印二叉树&lpar;二叉树的层次遍历BFS&rpar; 题解

    剑指offer  面试题23:从上往下打印二叉树 参与人数:4853  时间限制:1秒  空间限制:32768K 提交网址: http://www.nowcoder.com/practice/7fe2 ...

  3. 畅通工程(自己写的BFS,但后面想了下并查集更好更快)

    某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省*“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可). ...

  4. AcWing:177&period; 噩梦(bfs)

    给定一张N*M的地图,地图中有1个男孩,1个女孩和2个鬼. 字符“.”表示道路,字符“X”表示墙,字符“M”表示男孩的位置,字符“G”表示女孩的位置,字符“Z”表示鬼的位置. 男孩每秒可以移动3个单位 ...

  5. HDU 1560 DNA sequence &lpar;IDA&ast; 迭代加深 搜索&rpar;

    题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1560 BFS题解:http://www.cnblogs.com/crazyapple/p/321810 ...

  6. 洛谷P1605走迷宫

    传送 这是一道dfs,但是...但是....但是它竟然被放在bfs练习题辣!!!! 打了半天bfs,发现路径不会标记了,于是发现好像有什么不对的,似乎dfs要简单一点,于是半路跑去打dfs,结果打了半 ...

  7. 记 2020蓝桥杯校内预选赛&lpar;JAVA组&rpar; 赛后总结

    目录 引言 结果填空 1. 签到题 2. 概念题 3. 签到题 4. 签到题 程序题 5. 递增三元组[遍历] 6. 小明的hello[循环] 7. 数位递增[数位dp] 8. 小明家的草地[bfs] ...

  8. &OpenCurlyDoubleQuote;盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛题解&amp&semi;&amp&semi;源码【A&comma;水&comma;B&comma;水&comma;C&comma;水&comma;D&comma;快速幂&comma;E&comma;优先队列&comma;F&comma;暴力&comma;G&comma;贪心&plus;排序&comma;H&comma;STL乱搞&comma;I&comma;尼姆博弈&comma;J&comma;差分dp&comma;K&comma;二分&plus;排序&comma;L&comma;矩阵快速幂&comma;M&comma;线段树区间更新&plus;Lazy思想&comma;N&comma;超级快速幂&plus;扩展欧里几德&comma;O&comma;BFS】

    黑白图像直方图 发布时间: 2017年7月9日 18:30   最后更新: 2017年7月10日 21:08   时间限制: 1000ms   内存限制: 128M 描述 在一个矩形的灰度图像上,每个 ...

  9. HDU1043 Eight(八数码:逆向BFS打表&plus;康托展开)题解

    Eight Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Sub ...

随机推荐

  1. nginx for linux安装及安装错误解决

    nginx:下载地址:http://www.nginx.org/ 1.GCC编译器 安装指令 :yum  install -y  gcc 如果你所使用的是ubuntu,则安装指令为:apt-get i ...

  2. NBUT 1673 迷宫问题(DP)

    [1673] 迷宫问题 时间限制: 1000 ms 内存限制: 65535 K 问题描述 Alex的猫咪不小心走进了迷宫,Alex为了心爱的猫咪,决定进入迷宫去解救他的猫咪. 已知猫咪坐标为(n - ...

  3. WordPress Design Approval System插件&OpenCurlyQuote;step’参数跨站脚本漏洞

    漏洞名称: WordPress Design Approval System插件‘step’参数跨站脚本漏洞 CNNVD编号: CNNVD-201309-084 发布时间: 2013-09-11 更新 ...

  4. mysq开启慢查询

    1 将未建立索引的sql放到慢查询日志中 查看 log_queries_not_using_indexes 是否为on show variables like 'log%'; 将 log_querie ...

  5. H5 input输入限制最大位数,和调用小键盘需求发生冲突的解决办法

    首先,限制输入最大位数时,input有自带的属性maxlength. <input type="text" name="email" maxlength= ...

  6. Node笔记五-进程、线程

    进程 -每一个正在运行的应用程序都称之为进程 -每一个应用程序都至少有一个进程 -进程是用来给应用程序提供一个运行的环境 -进程是操作系统为应用程序分配资源的一个单位线程 -用来执行应用程序中的代码 ...

  7. 简单数论之整除&amp&semi;质因数分解&amp&semi;唯一分解定理

    [整除] 若a被b整除,即a是b的倍数,那么记作b|a("|"是整除符号),读作"b整除a"或"a能被b整除".b叫做a的约数(或因数),a ...

  8. C&num;字符串转二进制、二进制转字符串

    最近公司要做一个操作日志的模块,如果将操作日志以字符串的形式存到后台数据库,非常浪费内存,不可取,特意写了字符串与二进制相互转换的函数. 1.字符串转二进制 private string String ...

  9. Tesseract 引擎翻译

    Tesseract 引擎翻译 Category: 图像识别 Last Edited: Sep 17, 2018 10:29 AM Tags: tesseract,字符识别,翻译 1.英文原文(中文翻译 ...

  10. 如何使不同时区的时间与京8区一致?(JS实现)

    如何使不同时区的时间与京8区一致?(JS实现) Update:2019/1/28 更简单的是使用这个函数(toDate): // 自定义日期格式如下(年月日都必须提供): // "2011- ...