一道模拟题 (卡了我好久)
题中要求判断不改变镜子或者只改变一次镜子能否从起点到达终点
所以我们可以模拟一遍原图,如果能够到达终点就直接输出0
如果原图不能到达终点就从第一个镜子开始改变,然后再模拟一遍,模拟完记得状态还原
用fw表示前进方向,st表示经过某个镜子的次数
fw的0 1 2 3分别表示上右下左
(新加了三组数据,可以ac)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef pair<int, int> PII;
const int N = 250, Null = 0x3f3f3f3f;
int n, a, b;
int res = Null;
int st[N];
PII mp[N];//保存镜子坐标
char g[N];//保存镜子状态
//判断是否可以到达终点
bool check(int x, int y, int fw)
{
return (fw == 0 && x == a && y < b || fw == 1 && y == b && x < a
|| fw == 2 && x == a && y > b || fw == 3 && y == b && x > a);
}
bool walk(int x, int y, int fw, int u)
{
int minx = Null, idx = 0;
for (int i = 1; i <= n; i++)
{
if (st[i] > 2) return false;//可能有镜子会重复使用,同时要防止死循环
/*
* 分析一下情况可以发现如果使用同一面反射,光线是同一条
* 所以镜子的一面不能重复使用
* 如果使用同一面镜子超过2次就说明至少有一面是重复使用过的
* 这种情况是一定存在闭合环的,需要排除这种情况
* 所以st[i] > 2时就一定存在闭合环
*/
int x1 = mp[i].first, y1 = mp[i].second;
if ((fw == 1 && y1 == y && x1 > x) || (fw == 3 && y1 == y && x1 < x))
{ if (minx > abs(x - x1)) minx = abs(x - x1), idx = i; }
else if ((fw == 2 && x1 == x && y1 < y) || (fw == 0 && x1 == x && y1 > y))
{ if (minx > abs(y - y1)) minx = abs(y - y1), idx = i; }
//找到当前方向最近的镜子,并保存该镜子的序号
else continue;//如果当前方向没有镜子就跳过
}
int da = abs(a - x), db = abs(b - y);//计算当前点距离终点的水平、竖直距离
if ((!da && db < minx) || (!db && da < minx))
//x或y坐标与终点相同,且和终点之间没有被镜子隔开就判断一下能否到达终点
{
if (check(x, y, fw))
{
res = u;//将当前修改的镜子序号设为答案
return true;//如果能到达终点就结束循环
}
}
if (minx != Null)
{
st[idx]++;
if (g[idx] == '/') fw ^= 1;
else fw ^= 3;//根据镜子的状态改变方向
return walk(mp[idx].first, mp[idx].second, fw, u);//深搜
}
else return false;//如果不能到达终点就结束
}
int main()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
{
int x, y;
char s;
cin >> x >> y >> s;
mp[i] = { x, y };//保存坐标
g[i] = s;//保存状态
}
bool flag = walk(0, 0, 1, 0);//不改变镜子的情况下模拟一次
for (int i = 1; i <= n && !flag; i++)
{
memset(st, 0, sizeof st);
if (g[i] == '/') g[i] = '\\';
else g[i] = '/';//改变第i个镜子并模拟
flag = walk(0, 0, 1, i);
if (g[i] == '/') g[i] = '\\';
else g[i] = '/';//将第i个镜子状态还原
}
if (res == Null) cout << -1 << endl;
else cout << res << endl;
return 0;
}
无注释代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef pair<int, int> PII;
const int N = 250, Null = 0x3f3f3f3f;
int n, a, b;
int res = Null;
int st[N];
PII mp[N];
char g[N];
bool check(int x, int y, int fw)
{
return (fw == 0 && x == a && y < b || fw == 1 && y == b && x < a
|| fw == 2 && x == a && y > b || fw == 3 && y == b && x > a);
}
bool walk(int x, int y, int fw, int u)
{
int minx = Null, idx = 0;
for (int i = 1; i <= n; i++)
{
if (st[i] > 2) return false;
int x1 = mp[i].first, y1 = mp[i].second;
if ((fw == 1 && y1 == y && x1 > x) || (fw == 3 && y1 == y && x1 < x))
{ if (minx > abs(x - x1)) minx = abs(x - x1), idx = i; }
else if ((fw == 2 && x1 == x && y1 < y) || (fw == 0 && x1 == x && y1 > y))
{ if (minx > abs(y - y1)) minx = abs(y - y1), idx = i; }
else continue;
}
int da = abs(a - x), db = abs(b - y);
if ((!da && db < minx) || (!db && da < minx))
{
if (check(x, y, fw))
{
res = u;
return true;
}
}
if (minx != Null)
{
st[idx]++;
if (g[idx] == '/') fw ^= 1;
else fw ^= 3;
return walk(mp[idx].first, mp[idx].second, fw, u);
}
else return false;
}
int main()
{
cin >> n >> a >> b;
for (int i = 1; i <= n; i++)
{
int x, y;
char s;
cin >> x >> y >> s;
mp[i] = { x, y };
g[i] = s;
}
bool flag = walk(0, 0, 1, 0);
for (int i = 1; i <= n && !flag; i++)
{
memset(st, 0, sizeof st);
if (g[i] == '/') g[i] = '\\';
else g[i] = '/';
flag = walk(0, 0, 1, i);
if (g[i] == '/') g[i] = '\\';
else g[i] = '/';
}
if (res == Null) cout << -1 << endl;
else cout << res << endl;
return 0;
}
代码过不去ac不了
在check前加了一个当前点和终点之间是否有镜子的判断,现在可以ac了
突然想到一点,就是如果这个点已经用过两次了,那么就continue,如果这个点刚好的它这个方向上面最近的点,然后被continue了,然后下面的代码不是还会寻找这个方向上面最近的点嘛,那他把这个最近的点已经continue了,那他会找更远的点,这样会不会有问题呢,有点不明白这个点
能够跳过最近的镜子,看到镜子后面的镜子吗
这里确实不太严谨,如果同一面镜子使用超过两次就是存在环的,所以一面镜子使用超过两次直接返回false就可以了
判断是否存在环改成if (st[i] > 2) return false;
if (st[i] >= 2) continue;
,大佬能说一下为什么这句可以避免进入环中死循环嘛有一组样例会反复在几个镜子之间来回反射,如果同一个镜子反射次数过多就是进入死循环了
这里可以稍微写大一点,后来测试样例发现2就可以过
输入样例
20 17 -17
5 0 /
5 5 \
0 5 \
0 -5 \
5 -5 /
10 0 \
10 -10 \
11 -10 \
11 -11 \
12 -11 \
12 -12 \
13 -12 \
13 -13 \
14 -13 \
14 -14 \
15 -14 \
15 -15 \
16 -15 \
16 -16 \
17 -16 \
输出样例
3
这个样例就有镜子需要用到两次
一个镜子用了4次及以上,就肯定在环内,能不能这样理解呀
确实是这样,用了4次的话上下左右四个方向都用过,如果超过四次就一定是存在一个闭合环的
仔细想了一下,其实2次就可以完全判断是否有闭合环了,使用镜子的同一面进行反射的话光线是同一条,也就是路线是完全相同的,这种情况就是进入死循环了。同一个镜子最多每个面反射一次,多一次就一定存在循环
似乎不可能在镜子同一面的两个方向都进行反射,那么最多在镜子的两面各反射一次,一共2次,超过就是在环中.
是的
这个答案为什么是3呢
从起点往右看,只有把3号改一下方向才能到终点