题目描述
众所周知，瑞神已经达到了CS本科生的天花板，但殊不知天外有天，人外有苟。在浩瀚的宇宙中，存在着一种叫做苟狗的生物，这种生物天生就能达到人类研究生的知识水平，并且天生擅长CSP，甚至有全国第一的水平！但最可怕的是，它可以发出宇宙射线！宇宙射线可以摧毁人的智商，进行降智打击！宇宙射线会在无限的二维平面上传播（可以看做一个二维网格图），初始方向默认向上。宇宙射线会在发射出一段距离后分裂，向该方向的左右45°方向分裂出两条宇宙射线，同时威力不变！宇宙射线会分裂 次，每次分裂后会在分裂方向前进 个单位长度。现在瑞神要带着他的小弟们挑战苟狗，但是瑞神不想让自己的智商降到普通本科生 那么菜的水平，所以瑞神来请求你帮他计算出共有多
少个位置会被"降智打击"
输入描述
输入第一行包含一个正整数 ，表示宇宙射线会分裂几次
第二行包含n个正整数 ，第ai个数表示第 i次分裂的宇宙射线会在它原方向上继续走多少个单位长度。
输出描述
输出一个数 ，表示有多少个位置会被降智打击
样例输入
4
4 2 2 3
样例输出
39
BFS思路
如上图，模拟射线进行前进，但是必须做简化，否则会超时。
选用记忆化搜索；
详细见代码注释
BFS代码
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include<queue>
using namespace std;
int m_x[] = { 0,1,1, 1, 0, -1, -1, -1 };
int m_y[] = { 1,1,0,-1,-1, -1, 0, 1 };
int n;
int a[35];
int mp[350][350] = { 0 }; //地图
int vis[350][350][35][9] = { 0 }; //用于记忆化搜素
int ans = 0;
struct position //存储当前点的信息
{
int x;
int y;
int n;
int dir;
};
queue<position> q; //bfs用到队列
void bfs()
{
while (!q.empty())
{
position now = q.front();
q.pop();
for (int i = 1; i <= a[now.n]; i++)
{
now.x += m_x[now.dir];
now.y += m_y[now.dir];
if (!mp[now.x][now.y])
{
mp[now.x][now.y] = 1;
ans++;
}
}
//向两边发散 记忆化判断
if (!vis[now.x][now.y][(now.n) + 1][(now.dir + 1) % 8]&&now.n+1<=n)
{
vis[now.x][now.y][(now.n) + 1][(now.dir + 1) % 8] = 1;
q.push({ now.x,now.y,now.n + 1,(now.dir + 1) % 8 });
}
if (!vis[now.x][now.y][(now.n) + 1][(now.dir + 7) % 8] && now.n + 1 <= n)
{
vis[now.x][now.y][(now.n) + 1][(now.dir + 7) % 8] = 1;
q.push({ now.x,now.y,now.n + 1,(now.dir + 7) % 8 });
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
position now;
now.x = 160;
now.y = 160;
now.n = 1;
now.dir = 0;
q.push(now);//起始点
bfs();
printf("%d\n", ans);
return 0;
}
DFS思路
这个思路是大佬给的启发(手动感谢大佬）。
由于射线的规律性，每次都向两边分散45°，所以一共走八个方向。我们可以每次只走一个方向，走到底后在向后退，每退到一个方向，就沿着上一个来的方向求当前图形的对称！
如图(只举例三步，画画能力有限），首先是红色深度优先遍历到底1 ，2，3(我们规定每次只走右边),
然后回退，首先是第三步关于第二步的对称，在然后是第二步关于第一步的对称。
起始DFS更像是递归求对称。
DFS代码
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;
bool a[1600][1600] = { 0 };
int b[35];
int m_x[] = {0,1,1, 1, 0, -1, -1, -1}; //八个行动方向 从向北开始 顺时针走
int m_y[] = {1,1,0,-1,-1, -1, 0, 1};
int ans=0;
int n;
struct position
{ //记录所到位置 及求出的对称点的位置
int x;
int y;
position(){}
position(int &_x, int &_y)
{
x = _x;
y = _y;
}
};
list<position> c; //dfs
list<position> d; //回退到的点
//这里为什么用list不用vector 见文末解释。
void symmetry(position& s, int dir)
{//求对称 s 当前位置 dir 上一个方向
position* tmp=new position();
if ( dir %8 ==2 || dir % 8 == 6)//关于 平行于x轴的轴 的对称
{
for (auto it = d.begin(); it != d.end();it++)
{//遍历求当前所有回退到的点的对称
tmp->x= (*it).x; tmp->y = 2 * (s.y) - (*it).y; //对称公式(擅用搜索引擎)
if (a[tmp->x][tmp->y]== 0)
{//如果没被放问过 访问并计数
a[tmp->x][tmp->y] = 1;
ans++;
d.push_front(position(tmp->x, tmp->y)); //加入回退到的序列当中
}
}
}y
else if (dir % 8 == 0 || dir % 8 == 4)//关于 平行于y轴的轴 的对称
{
for (auto it = d.begin(); it !=d.end(); it++)
{
tmp->x = 2 * (s.x) - (*it).x; tmp->y = (*it).y;
if (a[tmp->x][tmp->y] == 0)
{
a[tmp->x][tmp->y] = 1;
ans++;
d.push_front(position(tmp->x, tmp->y));
}
}
}
else if (dir % 8 == 1 || dir % 8 == 5)//关于 平行于x=y轴的轴 的对称
{
for (auto it = d.begin(); it != d.end() ; it++)
{
tmp->x =(*it).y-s.y+s.x; tmp->y = (*it).x +s.y - s.x;
if (a[tmp->x][tmp->y] == 0)
{
a[tmp->x][tmp->y] = 1;
ans++;
d.push_front(position(tmp->x, tmp->y));
}
}
}
else if (dir % 8 == 3 || dir % 8 == 7 )//关于 平行于x=-y轴的轴 的对称
{
for (auto it = d.begin(); it != d.end(); it++)
{
tmp->x =s.y + s.x-(*it).y ; tmp->y = s.y +s.x - (*it).x;
if (a[tmp->x][tmp->y] == 0)
{
a[tmp->x][tmp->y] = 1;
ans++;
d.push_front(position(tmp->x, tmp->y));
}
}
}
}
void DFS(position s, int len, int dir)
{
if (len < n)
{
for (int i = 0; i < b[len]; i++)
{
s.x += m_x[dir];
s.y += m_y[dir];
c.push_front(position(s.x,s.y));
}
if (len == n - 1)
{//最后一次 递归终点
for (int i = 0; i < b[len]; i++)
{
d.push_front(c.front());
if (a[c.front().x][c.front().y] == 0)
{
a[c.front().x][c.front().y] = 1;
ans++;
}
c.pop_front();
}m_x,m_y
return;
}
DFS(s,len+1,(dir+1)%8); //(dir+1)%8 对照m_x,m_y求下一次向右的方向
//DFS深度遍历
symmetry(s,dir); //将回退到当前图形的图对称
for (int i = 0; i < b[len]; i++)
{ //回退c中的序列
d.push_front(c.front());
if (a[c.front().x][c.front().y] == 0)
{
a[c.front().x][c.front().y] = 1;
ans++;
}
c.pop_front();
}
}
else
return;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &b[i]);
}
position ini;
ini.x = 800;
ini.y = 800;
c.push_front(ini);
DFS(ini, 0, 0);
cout << ans << endl;
return 0;
}
DFS代码二
上课提供的代码，思路类似于BFS，记忆化搜索。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
using namespace std;
int m_x[] = { 0,1,1, 1, 0, -1, -1, -1 }; //x,y 移动方向
int m_y[] = { 1,1,0,-1,-1, -1, 0, 1 };
int n; //操作数
int a[35];
int mp[350][350]={0}; //地图
int vis[350][350][35][9]={0}; //记忆化记录
int ans=0;
void dfs(int x,int y,int j,int d)
{
if(vis[x][y][j][d]) return;
vis[x][y][j][d]=1;
for(int i=1;i<=a[j];i++)
{
x+=m_x[d];y+=m_y[d];
if(!mp[x][y])
{
ans++;
mp[x][y]=1;
}
}
if(j<n)
{
dfs(x,y,j+1,(d+1)%8);
dfs(x,y,j+1,(d+7)%8);
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
dfs(160,160,1,0);
printf("%d\n",ans);
return 0;
}
总结
1，dfs时为什么用list不用vector
刚开始用的vector，但是同样的思路 怎么写都不对 后来经过输出测试(菜鸟不会debug，只会cout测试);
经过测试，用vector的迭代器遍历的时候，不能在里面加入元素，否则vector的end()迭代器会失效，导致不能正常访问。
总结：vector迭代器的几种失效的情况：
1.当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。
2.当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操
作返回的迭代器都会失效。
3.当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。
2，BFS常规一定会超时，所以选用记忆化搜索。
转载自原文链接, 如需删除请联系管理员。
原文链接：c++实现——宇宙射线，转载请注明来源！