网站建设相关合同内容,云和网站建设,永久域名网站,wordpress 访问控制题目链接#xff1a;Golygons 题目描述#xff1a; 给定nnn和kkk个障碍物的坐标#xff0c;你需要走nnn次#xff0c;第一次走一个单位距离#xff0c;第二次走二个单位距离#xff0c;…#xff0c;第nnn次走nnn个单位距离。走得过程中不能穿过或者到达障碍物所在的点Golygons 题目描述 给定nnn和kkk个障碍物的坐标你需要走nnn次第一次走一个单位距离第二次走二个单位距离…第nnn次走nnn个单位距离。走得过程中不能穿过或者到达障碍物所在的点你走得方向为东南西北也就是上下左右但是需要注意的是你每走一步你必须进行一次90°90\degree90°的转向输出所有能够从(0,0)(0,0)(0,0)出发并且回到(0,0)(0,0)(0,0)位置的路径。 例如下图是一种合理的路径。 输出用newsnewsnews组成的字母表示。 题解 本题我们从原点开始搜索下一次移动后的位置并且我们判断移动路径上是否存在障碍物如果不存在我们才能移动同时需要判断到达的点我们之前是否到达过。这样在nnn次移动之后我们只需要判断是否回到了原点。 可以使用的剪枝如果我们当前位置的横纵坐标的和大于剩下可以走得步数那么我们可以直接进行剪枝。 代码 注最好不用STLSTLSTL我开始用STLSTLSTL如果不开O2O2O2的话会超时
#include bits/stdc.hconst int MAX_COORDINATE (1 20) * 20 / 2 / 2; // 移动要想回到原点最多20步走的最大距离的一半
const int o MAX_COORDINATE; // 为了处理负数我们将所有的坐标全部进行一次移动using namespace std;int T, n, k, x, y, ans;
bool block[(MAX_COORDINATE 1) 1][(MAX_COORDINATE 1) 1], vis[(MAX_COORDINATE 1) 1][(MAX_COORDINATE 1) 1];
string path;// 按字典序从小到大返回direction转向90度形成的方向
string getDirection(char direction)
{if (direction 0) { return ensw; }else if (direction e) { return ns; }else if (direction s) { return ew; }else if (direction w) { return ns; }else { return ew; }
}// 朝某个方向走step步
void move(int x, int y, char direction, int step)
{if (direction e) { x step; }else if (direction w) { x - step; }else if (direction n) { y step; }else { y - step; }
}// 判断路径上是否有障碍物
bool blocked(int a1, int b1, int a2, int b2)
{if (a1 a2) {if (b1 b2) { swap(b1, b2); }while(b1 b2) {if (block[a1][b1]) { return true; }b1;}} else if (b1 b2) {if (a1 a2) {swap(a1, a2); }while(a1 a2) {if (block[a1][b1]) { return true; }a1;}}return false;
}void dfs(int nowDepth, char lastDirection)
{if (nowDepth n) {if (x o y o) {ans;cout path endl;}return;}if (abs(x - o) abs(y - o) - (nowDepth 1 n) * (n - nowDepth) / 2 0) { return; }string direction getDirection(lastDirection);for (char nowDirection : direction) {int tempX x, tempY y;int nx x, ny y;move(nx, ny, nowDirection, nowDepth 1);if (vis[nx][ny] || blocked(x, y, nx, ny)) { continue; }vis[nx][ny] true;x nx, y ny;path.push_back(nowDirection);dfs(nowDepth 1, nowDirection);vis[nx][ny] false;x tempX, y tempY;path.pop_back();}
}int main()
{ios::sync_with_stdio(false);cin T;while(T--) {cin n k;memset(vis, 0, sizeof(vis));memset(block, 0, sizeof(block));for (int i 0; i k; i) {cin x y;if (abs(x) MAX_COORDINATE || abs(y) MAX_COORDINATE) { continue; } // 在范围外的不论如何都不会撞到block[x MAX_COORDINATE][y MAX_COORDINATE] true;}ans 0;x y o;path ;dfs(0, 0);cout Found ans golygon(s). endl endl;}return 0;
}
