noip题有bug，求找出
noip题有bug，求找到
http://www.luogu.org/problem/show?pid=1126#
题目描述
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式：
输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式：
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。
输入输出样例
输入样例#1：
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S
输出样例#1：
12
我的代码
找啦好久也没找出bug。
------解决思路----------------------
蛋疼的是调试别人的代码, 最蛋疼的别人的代码写得很乱.还不如自己写,
用的c++11/14, 所以g++要打开c++14的编译选项, 很遗憾没能提交看看是否正确.
首先说一下, 一下就能看到
这个错误, 在编写途中注意到一些:
1. 题目很蛋疼, 先输入Y轴再输入X轴.
2. 检查是否通过不能只检查终点, 因为一次性走3格就可能跨过一个障碍物
3. 很久没写这种题了, 花了2+小时
最后上代码,
http://www.luogu.org/problem/show?pid=1126#
题目描述
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式：
输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式：
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。
输入输出样例
输入样例#1：
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S
输出样例#1：
12
我的代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
struct et
{ int x;
int y;
int turn;
int time;
};
int turnx[4]={1,0,-1,0},turny[4]={0,-1,0,1},mp[50][50],n,m,ex,ey,t=10000;
int td[4][4]={{0,1,2,1},{1,0,1,2},{2,1,0,1},{1,2,1,0}},vis[50][50];//td转向时间
void bfs(int fy,int fx,int ft)
{ et acz;
acz.x=fx,acz.y=fy,acz.turn=ft,acz.time=0;
queue<et> q;
q.push(acz);
vis[fy][fx]=1;
while(!q.empty())
{ et fa=q.front();
q.pop();
if(fa.x==ex&&fa.y==ey&&t>fa.time)t=fa.time;
for(int i=0;i<4;i++)
{ et son;
son.time=fa.time+td[fa.turn][i]+1;
son.turn=i;
for(int j=1;j<=3;j++)
{
son.x=fa.x+turnx[i]*j;
son.y=fa.y+turny[i]*j;
if(son.x<0||son.x>=m||son.y<0||son.y>=n)break;
if(vis[son.y][son.x]==1)continue;
if(mp[son.y][son.x]==1)break;
vis[son.y][son.x]=1;
q.push(son);
};
};
};
if(t==10000)cout<<"-1"<<endl;
else cout<<t<<endl;
}
int main()
{ cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>mp[i][j];
int fx,fy,ft;
char xxx;
memset(vis,0,sizeof(vis));
cin>>fy>>fx>>ey>>ex>>xxx;
if(xxx='E')ft=0;
else if(xxx='S')ft=1;
else if(xxx='W')ft=2;
else if(xxx='N')ft=3;
bfs(fy,fx,ft);
return 0;
}
找啦好久也没找出bug。
------解决思路----------------------
蛋疼的是调试别人的代码, 最蛋疼的别人的代码写得很乱.还不如自己写,
用的c++11/14, 所以g++要打开c++14的编译选项, 很遗憾没能提交看看是否正确.
首先说一下, 一下就能看到
if(xxx='E')ft=0;
else if(xxx='S')ft=1;
else if(xxx='W')ft=2;
else if(xxx='N')ft=3;
这个错误, 在编写途中注意到一些:
1. 题目很蛋疼, 先输入Y轴再输入X轴.
2. 检查是否通过不能只检查终点, 因为一次性走3格就可能跨过一个障碍物
3. 很久没写这种题了, 花了2+小时
最后上代码,
#include <cstdint>
#include <cstdio>
#include <vector>
constexpr size_t MAP_SIZE_MAX = 50;
enum Direction : uint16_t { DirectionE = 0, DirectionS, DirectionW, DirectionN };
struct bot_state { int8_t x; int8_t y; Direction d; };
bool operator ==(const bot_state& a, const bot_state& b) noexcept {
return reinterpret_cast<const uint32_t&>(a) == reinterpret_cast<const uint32_t&>(b);
}
struct game_state { bot_state s; int width; int height; int end_x; int end_y; bool* map; };
int bot_search(const game_state& g) noexcept;
int main() {
bool map[MAP_SIZE_MAX*MAP_SIZE_MAX];
int width = 0, height = 0;
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
char direction = 0 ;
std::scanf("%d %d\n", &height, &width);
for (auto i = 0; i < width*height; ++i) {
int tmp = 0; std::scanf("%d", &tmp); map[i] = !tmp;
}
std::scanf("%d %d %d %d %c", &y1, &x1, &y2, &x2, &direction);
auto get_d = [=]() {
switch (direction) {
case 'E': return DirectionE;
case 'S': return DirectionS;
case 'W': return DirectionW;
default: return DirectionN;
}
};
game_state game = { { int8_t(x1), int8_t(y1), get_d() }, width, height, x2, y2, map };
std::printf("%d", bot_search(game));
return 0;
}
const int FORWORD[] = { 1, 0, 0, 1, -1, 0, 0, -1 };
const Direction TURN[] = { DirectionS, DirectionN, DirectionW, DirectionE, DirectionN, DirectionS, DirectionE, DirectionW };
int bot_search(const game_state& g) noexcept {
static game_state game; game = g;
std::vector<bot_state> bot_states;
std::vector<bot_state> bot_states_tmp;
std::vector<bot_state> history;
try {
bot_state tmp;
auto isok = [&tmp]() noexcept {
return tmp.x == game.end_x && tmp.y == game.end_y;
};
auto push_state = [&history, &bot_states_tmp, &tmp]() {
for (const auto& s : history) {
if (s == tmp) return;
}
bot_states_tmp.push_back(tmp);
history.push_back(tmp);
};
auto test = [&tmp]() noexcept {
if (tmp.x <= 0
------解决思路----------------------
tmp.x >= game.width
------解决思路----------------------
tmp.y <= 0
------解决思路----------------------
tmp.y >= game.height) return false;
if (tmp.x == 1 && tmp.y == 6) {
int bk = 9;
}
auto basic_pos1 = tmp.y * game.width + tmp.x;
auto basic_pos2 = basic_pos1 - game.width;
return game.map[basic_pos1] && game.map[basic_pos2] && game.map[basic_pos1 - 1] && game.map[basic_pos2 - 1];
};
auto forword = [&tmp]() {
tmp.x += FORWORD[tmp.d * 2];
tmp.y += FORWORD[tmp.d * 2 + 1];
};
auto turn = [&tmp](int right) { tmp.d = TURN[tmp.d * 2 + right]; };
bot_states.reserve(1000);
history.reserve(1000);
bot_states_tmp.reserve(1000);
bot_states.push_back(game.s);
history.push_back(game.s);
int time = 1;
for (;;++time) {
if (bot_states.empty()) break;
for (const auto& state : bot_states) {
// -> -> ->
tmp = state;
for (auto i = 0; i < 3; ++i) {
forword();
if (isok()) return time;
else if (test()) push_state();
else break;
}
// >
tmp = state; turn(1);
if (isok()) return time;
if (test()) push_state();
// <
tmp = state; turn(0);
if (isok()) return time;
if (test()) push_state();
}
bot_states.swap(bot_states_tmp);
bot_states_tmp.clear();
}
}
catch (...) {
return -1;
}
return -1;
}