文章目录
- 题目描述
- 输入
- 输出
- 样例输入
- 样例输出
- 思路
- 综述
- 剪枝条件（满足以下条件，b点之后的可以忽略）：
- 如何建立二维地图
- 记忆化搜索需要的数组
- 方向表示
- 过程
-
- 总结
- 代码
-
题目描述
众所周知，瑞神已经达到了CS本科生的天花板，但殊不知天外有天，人外有苟。在浩瀚的宇宙中，存在着一种叫做苟狗的生物，这种生物天 生就能达到人类研究生的知识水平，并且天生擅长CSP，甚至有全国第一的水平！但最可怕的是，它可以发出宇宙射线！宇宙射线可以摧毁 人的智商，进行降智打击！ 宇宙射线会在无限的二维平面上传播（可以看做一个二维网格图），初始方向默认向上。宇宙射线会在发射出一段距离后分裂，向该方向的 左右45°方向分裂出两条宇宙射线，同时威力不变！宇宙射线会分裂 次，每次分裂后会在分裂方向前进 个单位长度。 现在瑞神要带着他的小弟们挑战苟狗，但是瑞神不想让自己的智商降到普通本科生 那么菜的水平，所以瑞神来请求你帮他计算出共有多 少个位置会被"降智打击"
输入
| 输入第一行包含一个正整数 ，表示宇宙射线会分裂 次 第二行包含n个正整数 ，第i个数 表示第ai次分裂的宇宙射线会在它原方向上继续走多少个单位长度。 |
输出
样例输入
样例输出
思路
综述
这是一道模拟题，利用到图论的知识，根据数据量来看，单靠暴力的dfs和bfs并不能满足，会超时。所以需要剪枝；
如何剪枝
剪枝条件（满足以下条件，b点之后的可以忽略）：
（a、b两条射线起始点，假设a在b前面）
1）b点和a点x，y坐标相同；
2）a点和b点的分裂的次数相同；
3）a点和b点的分裂的方向相同；
如何建立二维地图
由于分裂的次数最大是30次，每次移动的距离小于等于5，所以，在一个方向上的延伸不会超过150，所以建立300*300的二维地图足够用
记忆化搜索需要的数组
四维变量vis[x][y][a][d]
第一维和第二维用于记录该点的位置；
第三维用于记录该点的分裂的次数；
第四维用于记录该点分裂方向；
方向表示
0–7 分别表示右、右上、上、左上、左、左下、下、右下。
每一对dx[i],dy[i]用于记录某个方向的x和y的变化
int dx[] = { 1,1,0,-1,-1,-1,0,1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1 };
过程
Step1：
初始化：从(200,200)开始移动
开始的方向是向上
start.x = 200;
start.y = 200;
start.dir = 2;
start.num = 0;
Step2：
广度优先搜索的过程
while (!qq.empty())
元素出队
node now;
now = qq.front();
qq.pop();
进行剪枝，符合以下之一即可
1）符合综述里面的条件
2）该点分裂次数超过n
if (now.num > n) continue;
if (vis[now.x][now.y][now.num][now.dir])
continue;
记录分裂的信息，并且向着dir前进
vis[now.x][now.y][now.num][now.dir] = 1;
for (int i = 0; i < a[now.num]; i++) {
now.x += dx[now.dir];
now.y += dy[now.dir];
if (road[now.x][now.y] != 1) {
road[now.x][now.y] = 1;
tot++;
}
}
更新下两个方向的信息，并且入队
node next;
next.x = now.x;
next.y = now.y;
next.num = now.num+1;
next.dir = (now.dir + 1) % 8;
qq.push(next);
next.dir = (now.dir + 7) % 8;
qq.push(next);
总结
这道题目。本意是考察图的遍历算法并且剪枝的使用；但是据说可以用数学的方法解决，推式子，因为两边的分裂是对称的。
最开始做的时候，一心想要模拟这个过程，所以最后写出来一堆代码，大约300行，冗余重复，可读性极差，可修改性极差；与这道题想要考察的本意背道而驰；
数学中的应用题和计算机中的模拟题有一点是不同的，数学中的计算法基本上是固定的，通常想到算法，基本上就能够解决。
但是代码中的算法可以通过暴力求解来拿到一点点的分，这就导致了有很多题，拿过来就做，拿过来就模拟，导致复杂度高，可读性差，而且修改起来很是不方便；
代码
bfs做法：
#include <iostream>
#include <queue>
using namespace std;
int a[32];
int n;
int road[400][400];
int vis[400][400][32][8];
int tot = 0;
int dx[] = { 1,1,0,-1,-1,-1,0,1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1 };
struct node {
int x;
int y;
int num;
int dir;
};
void bfs() {
node start;
start.x = 200;
start.y = 200;
start.dir = 2;
start.num = 0;
queue<node> qq;
qq.push(start);
int number = 1;
while (!qq.empty()) {
node now;
now = qq.front();
qq.pop();
if (now.num > n) continue;
if (vis[now.x][now.y][now.num][now.dir])
continue;
vis[now.x][now.y][now.num][now.dir] = 1;
for (int i = 0; i < a[now.num]; i++) {
now.x += dx[now.dir];
now.y += dy[now.dir];
if (road[now.x][now.y] != 1) {
road[now.x][now.y] = 1;
tot++;
}
}
node next;
next.x = now.x;
next.y = now.y;
next.num = now.num+1;
next.dir = (now.dir + 1) % 8;
qq.push(next);
next.dir = (now.dir + 7) % 8;
qq.push(next);
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
bfs();
cout << tot << endl;
}
dfs做法：
#include <iostream>
#include <queue>
using namespace std;
int a[32];
int n;
int road[400][400];
int vis[400][400][32][8];
int tot = 0;
int dx[] = { 1,1,0,-1,-1,-1,0,1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1 };
struct node {
int x;
int y;
int num;
int dir;
};
void dfs(int x,int y,int num,int dir) {
if (num > n)return;
if (vis[x][y][num][dir])return;
vis[x][y][num][dir] = 1;
for (int i = 0; i < a[num]; i++) {
x += dx[dir];
y += dy[dir];
if (road[x][y] != 1) {
road[x][y] = 1;
tot++;
}
}
num++;;
dfs(x, y, num, ((dir + 1) % 8));
dfs(x, y, num, ((dir + 7) % 8));
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
dfs(200,200,0,0);
cout << tot << endl;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
