codingame
无聊登了一下condingame,通知说有本周谜题,正好刚撸完bfs,想尝试下。
题目链接:https://www.codingame.com/ide/17558874463b39b9ce6d420710807279bb1bd77e
题目大意:很有趣的题目,给你起始位置和终点位置,输出最短的路径,不过多了几个buff,垃圾球,开关,有害磁场
垃圾球:你可以移动(我没考虑这个东西,貌似用不到,因为后面说可以不动垃圾球)
开关:路过这个点,0/1状态变化一次
有害磁场:想通过磁场这个位置,必须把他关闭,方法是操作对应的开关
思路类似上一篇蓝桥杯迷宫还有poj3984
代码:
#include<cstdio>
#include <algorithm>
#include<queue>
#include<stack>
#include<cstring>
#define for(i, a, b) for(int i = a; i < b; i ++)//algorithm(要么不输入,输入必须在define前面,调换位置for的define会报错 using namespace std;
struct Node{
int r;
int c;
Node(int r, int c):r(r), c(c){}
Node(){}
}parent[][]; int dir[][] = {{, -}, {, }, {-, }, {, }};//上下左右
int main()
{
// freopen("C:\\Users\\GerJCS岛\\Desktop\\t.txt", "r", stdin);
int width;
int height;
int flag[][];
int step[][];
char str[][];
memset(flag, , sizeof(flag));
memset(parent, -, sizeof(parent));
memset(step, -, sizeof(step));
memset(str, '.', sizeof(str));
scanf("%d%d", &width, &height); getchar();
for(i, , height + ){//>=1 <= height
for(j, , width + )
scanf("%c", &str[j][i]);
getchar();
}
// for(i, 1, height + 1){//>=1 <= height
// for(j, 1, width + 1)
// printf("%c", str[j][i]);
// printf("\n");
// } int startX;
int startY;
scanf("%d%d", &startX, &startY);
int targetX;
int targetY;
scanf("%d%d", &targetX, &targetY); int switchCount;
scanf("%d", &switchCount);
int switchX;
int switchY;
int blockX;
int blockY;
int initialState; // 1 if blocking, 0 otherwise
for (i, , switchCount)
scanf("%d%d%d%d%d", &switchX, &switchY, &blockX, &blockY, &initialState);
//printf("%d %d %d %d\n", startX, startY, targetX, targetY); queue<Node> Q;
while(!Q.empty()) Q.pop();
Q.push(Node(startX, startY)); // printf("%d %d\n", Q.front().r, Q.front().c); flag[startX][startY] = ;
step[startX][startY] = ;//不算初始
int place;
while(!Q.empty()){
// printf("TEST\n");
Node node = Q.front();
Q.pop();//一开始忘了
int r = node.r;
int c = node.c;
for(i, , ){
int nowr = r + dir[i][];
int nowc = c + dir[i][];
// printf("%d%c%d\n", nowr, str[nowr][nowc], nowc);
if(nowr >= && nowc >= && nowr <= width && nowc <= height
&& !flag[nowr][nowc] && str[nowr][nowc] == '.'){
//printf("TEST\n");
flag[nowr][nowc] = ;
step[nowr][nowc] = step[r][c] + ;
Q.push(Node(nowr, nowc));
parent[nowr][nowc].r = r;
parent[nowr][nowc].c = c;
if(nowr == targetX && nowc == targetY){
place = step[nowr][nowc];
break;
}
}
}
} stack<char> S;//不用清空嘛
int r = width;
int c = height;
int r_r;
while(){
if(parent[r][c].r == - && parent[r][c].c == -)
break; if(parent[r][c].r < r)
S.push('R');
if(parent[r][c].r > r)
S.push('L');
if(parent[r][c].c < c)
S.push('D');
if(parent[r][c].c > c)
S.push('U'); r_r = parent[r][c].r;
c = parent[r][c].c;
r = r_r;//好蠢QAQ~
}
r = targetX; while(!S.empty()){
char pc = S.top();
S.pop();
printf("%c", pc);
}
printf("\n");
} //PS:这codingame的xy是反过来的,好别扭QAQ~,
//1,1 2,1
//1,2 2,2
//反手一想其实没什么影响,只是输出方向步伐,而不是坐标,就算是坐标也可以最后统一反向处理+增1操作
//打算把所有xy都调过来输入,在减一操作的
//想想还是算了,按题目来吧,不然不好调试,好反人类,,, //提示总线错误(莫名其妙没了。。。。) //写好后又是Standard Output Stream 什么都没有 /*
8 8
...#....
##.##.#.
.#..###.
.##.#...
..#.###.
.##...#.
..###.#.
........
1 1
8 8
0
*/
去注释代码:
#include<cstdio>
#include <algorithm>
#include<queue>
#include<stack>
#include<cstring>
#define for(i, a, b) for(int i = a; i < b; i ++) using namespace std;
struct Node{
int r;
int c;
Node(int r, int c):r(r), c(c){}
Node(){}
}parent[][]; int dir[][] = {{, -}, {, }, {-, }, {, }};//上下左右
int main()
{
freopen("C:\\Users\\GerJCS岛\\Desktop\\t.txt", "r", stdin);//这句话不注释会buss error
int width;
int height;
int flag[][];
int step[][];
char str[][];
memset(flag, , sizeof(flag));
memset(parent, -, sizeof(parent));
memset(step, -, sizeof(step));
memset(str, '.', sizeof(str));
scanf("%d%d", &width, &height); getchar();
for(i, , height + ){
for(j, , width + )
scanf("%c", &str[j][i]);
getchar();
}
int startX;
int startY;
scanf("%d%d", &startX, &startY);
int targetX;
int targetY;
scanf("%d%d", &targetX, &targetY); int switchCount;
scanf("%d", &switchCount);
int switchX;
int switchY;
int blockX;
int blockY;
int initialState; // 1 if blocking, 0 otherwise
for (i, , switchCount)
scanf("%d%d%d%d%d", &switchX, &switchY, &blockX, &blockY, &initialState); queue<Node> Q;
while(!Q.empty()) Q.pop();
Q.push(Node(startX, startY)); flag[startX][startY] = ;
step[startX][startY] = ;//不算初始
int place;
while(!Q.empty()){
Node node = Q.front();
Q.pop();//一开始忘了
int r = node.r;
int c = node.c;
for(i, , ){
int nowr = r + dir[i][];
int nowc = c + dir[i][];
if(nowr >= && nowc >= && nowr <= width && nowc <= height
&& !flag[nowr][nowc] && str[nowr][nowc] == '.'){
flag[nowr][nowc] = ;
step[nowr][nowc] = step[r][c] + ;
Q.push(Node(nowr, nowc));
parent[nowr][nowc].r = r;
parent[nowr][nowc].c = c;
if(nowr == targetX && nowc == targetY){
place = step[nowr][nowc];
break;
}
}
}
} stack<char> S;//不用清空嘛
int r = width;
int c = height;
int r_r;
while(){
if(parent[r][c].r == - && parent[r][c].c == -)
break; if(parent[r][c].r < r)
S.push('R');
if(parent[r][c].r > r)
S.push('L');
if(parent[r][c].c < c)
S.push('D');
if(parent[r][c].c > c)
S.push('U'); r_r = parent[r][c].r;
c = parent[r][c].c;
r = r_r;//好蠢QAQ~
}
r = targetX; while(!S.empty()){
char pc = S.top();
S.pop();
printf("%c", pc);
}
printf("\n");
} /*
第一组数据
8 8
...#....
##.##.#.
.#..###.
.##.#...
..#.###.
.##...#.
..###.#.
........
1 1 8 8 0
*/
PS:抱怨一下这个从1开始和xy反转这是反人类。。。
我第一次提示bus error莫名其妙就调没了,可能是第一次设置str为int类型
但是现在问题是跑1/30点的时候,平台的Standard Output Stream 什么都没有QAQ~,我输入题目1/30这组数据
...#....
##.##.#.
.#..###.
.##.#...
..#.###.
.##...#.
..###.#.
........
在本地是可以正确输出结果的QAQ~ (黑框输出的是:RRDDRDDDRRDDRR)
一会去撸铁,先放着。。
*********************更新**********************
真神奇,这道题只承认最后的cout里面的东西貌似。cout就好了,可是最后ans在本地也是对的,Standard Output却是个 0?的乱码
char ans[];
int i = ;
while(!S.empty()){
ans[i ++] = S.top();
S.pop();
}
// cout << "RRDDRDDDRRDDRRL" << endl;
cout << ans << endl;//本地可以,为啥Standard有提示怪怪的东西。。> 0?
// printf("\n");
最后这么改了下还是不行。。。
问了下作者原来是地图搞错了,https://www.codingame.com/forum/t/community-puzzle-bender-episode-4/84756/21(头像为山崎县人,ID为GerJCS的是我)
改下就好了,过了1/30数据,原来是从(0,0)开始的
代码:
#include<cstdio>
#include <algorithm>
#include<queue>
#include<iostream>
#include<stack>
#include<cstring>
#define for(i, a, b) for(int i = a; i < b; i ++) using namespace std;
struct Node{
int r;
int c;
Node(int r, int c):r(r), c(c){}
Node(){}
}parent[][]; int dir[][] = {{, -}, {, }, {-, }, {, }};//上下左右
char ans[];
int main()
{
// freopen("C:\\Users\\GerJCS岛\\Desktop\\t.txt", "r", stdin);//这句话不注释会buss error
int width;
int height;
int flag[][];
int step[][];
char str[][];
memset(flag, , sizeof(flag));
memset(parent, -, sizeof(parent));
memset(step, -, sizeof(step));
memset(str, '.', sizeof(str));
scanf("%d%d", &width, &height); getchar();
for(i, , height ){
for(j, , width )
scanf("%c", &str[j][i]);
getchar();
} // for(i, 0, height ){
// for(j, 0, width)
// printf("%c", str[j][i]);
// printf("\n");
// }
int startX;
int startY;
scanf("%d%d", &startX, &startY);
int targetX;
int targetY;
scanf("%d%d", &targetX, &targetY); int switchCount;
scanf("%d", &switchCount);
int switchX;
int switchY;
int blockX;
int blockY;
int initialState; // 1 if blocking, 0 otherwise
for (i, , switchCount)
scanf("%d%d%d%d%d", &switchX, &switchY, &blockX, &blockY, &initialState); // printf("%d %d %d %d\n", startX, startY, targetX, targetY); queue<Node> Q;
while(!Q.empty()) Q.pop();
Q.push(Node(startX, startY)); flag[startX][startY] = ;
step[startX][startY] = ;//不算初始
int place;
while(!Q.empty()){
Node node = Q.front();
Q.pop();//一开始忘了
int r = node.r;
int c = node.c;
for(i, , ){
int nowr = r + dir[i][];
int nowc = c + dir[i][];
if(nowr >= && nowc >= && nowr < width && nowc < height
&& !flag[nowr][nowc] && str[nowr][nowc] == '.'){
flag[nowr][nowc] = ;
step[nowr][nowc] = step[r][c] + ;
Q.push(Node(nowr, nowc));
parent[nowr][nowc].r = r;
parent[nowr][nowc].c = c;
if(nowr == targetX && nowc == targetY){
place = step[nowr][nowc];
break;
}
}
}
} stack<char> S;//不用清空嘛
int r = targetX;
int c = targetY;
int r_r;
while(){
if(parent[r][c].r == - && parent[r][c].c == -)
break; if(parent[r][c].r < r)
S.push('R');
if(parent[r][c].r > r)
S.push('L');
if(parent[r][c].c < c)
S.push('D');
if(parent[r][c].c > c)
S.push('U'); r_r = parent[r][c].r;
c = parent[r][c].c;
r = r_r;//好蠢QAQ~
}
// r = targetX; // memset(ans, '', sizeof(ans));
int i = ;
while(!S.empty()){
ans[i++ ] = S.top();
// printf("%c", ans[i ++]);
// cout << ans[i ++];//这两句都不行,不能单独输出,必须输出整个字符串,ans
S.pop();
// printf("%c", pc);
}
cout <<ans<< endl;
// ans[i] = '\0';
// cout << "RRDDRDDDRRDDRRL" << endl;
// cout << ans << endl;//本地可以,为啥Standard有提示怪怪的东西。。> 0?
// printf("\n");
} /*
第一组数据
8 8
...#....
##.##.#.
.#..###.
.##.#...
..#.###.
.##...#.
..###.#.
........
1 1 8 8 0 10 10
##########
#...#....#
###.##.#.#
#.#..###.#
#.##.#...#
#..#.###.#
#.##...#.#
#..###.#.#
#........#
##########
1 1
8 8
0 */
最新文章
- Could not load file or assembly &#39;Microsoft.ReportViewer.WebForms, Version=10.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a&#39; or one of its de
- Objective-C 观察者模式--简单介绍和使用
- [XAF] How to define a business class at runtime or allow end-users to configure its members via the application UI?
- 【BZOJ-1096】仓库建设 斜率优化DP
- Android 使用dip单位进行布局的一点知识
- 一步一步学习Unity3d学习笔记系1.2 单机游戏和网游的数据验证概念
- Android 当媒体变更后,通知其他应用重新扫描
- wpf MVVM ViewModel 关闭View显示
- 安装Python
- 纯IPv6环境App适配的坑
- Ubuntu安装ARM架构GCC工具链(ubuntu install ARM toolchain)最简单办法
- Activity的onSaveInstanceState()和onRestoreInstanceState()方法
- iOS面试题03-UI控件
- linux下apache 的安装
- 201521123059 《Java程序设计》第二周学习总结
- python学习日记(模块导入)
- pyspider
- Linux 文件内容查看(cat、tac、nl 、more 、less、head、tail )
- Visual Studio Code 学习记录
- centos7下源码安装多个nginx步骤完整版
热门文章
- RT-Thread—STM32—在线升级(Ymodem_OTA、HTTP_OTA)
- Jmeter与LoadRunner的比较
- 进阶 Linux基本命令-1
- Jenkins(2)- 更改插件源为国内源
- 深入理解TCP建立和关闭连接
- 防cc攻击利器之Httpgrard
- KVM 一键批量创建虚拟机
- web 之 session
- OpenWrt-19.07.2 For HC5861(极路由3) /HiWiFi/Gee最新固件,极路由3刷openwrt
- 【Netapp】在模拟器中使用disk removeowner报错