您的位置:首页 > 娱乐 > 明星 > 广西住房和城乡住建厅官网_网页设计html代码大全咋结啥_百度灰色词优化排名_推广关键词优化公司

广西住房和城乡住建厅官网_网页设计html代码大全咋结啥_百度灰色词优化排名_推广关键词优化公司

2024/12/23 10:21:52 来源:https://blog.csdn.net/qq278672818/article/details/142309230  浏览:    关键词:广西住房和城乡住建厅官网_网页设计html代码大全咋结啥_百度灰色词优化排名_推广关键词优化公司
广西住房和城乡住建厅官网_网页设计html代码大全咋结啥_百度灰色词优化排名_推广关键词优化公司

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

一道不难的题目,即使不用什么剪枝方法,也不会超时,可以AC的。

但是题目有一些隐含条件(或者说是我英语差一些,这道题的有些要求和题目背景放在一起描述,但是这个题目背景我没完全读懂)

首先要根据字典序输出,即'e', 'n', 's', 'w'

然后输入中哪些的阻碍的块是不能穿过的,即使移动起点和终点不在阻碍块上,只是中间路过也不行。

还有,已经访问过的块不能再次被访问,注意这里限制的是每次移动的起点和终点,中间路过已访问过的块是可以的,路过也不能称作“已访问”。

所以实际上是有两种逻辑不同的限制块类型。

AC代码

#include <stdio.h>
#include <string.h>
#define LINENUMMAX 22
#define MAXBLOCKNUM 51int lineNumMax;
// 当前的
int line[LINENUMMAX];
// 全部的
int totalNum;
int lintTotal[5000][LINENUMMAX];
// 已访问过的块
int map[500][500];// 序号从 1 开始
// n上 s下 e右 w左
// 数字 到 字母 字典序
char num2str[5] = {0, 'e', 'n', 's', 'w'};
// 方向对应的坐标移动
char steps[5][2] = {{}, {1, 0}, {0, 1}, {0, -1}, {-1, 0}};
// 方向对应的转90度方向
int truns[5][2] = {{}, {2, 3}, {1, 4}, {1, 4}, {2, 3}};void init()
{int i, x, y, n;scanf("%d", &lineNumMax);scanf("%d", &n);memset(map, 0, sizeof(map));memset(line, 0, sizeof(line));memset(lintTotal, 0, sizeof(lintTotal));for (i = 0; i < n; ++i){scanf("%d %d", &x, &y);map[x + 250][y + 250] = 2;}totalNum = 0;
}// 判断向当前方向走,会不会碰到阻碍 注意这里是移动之前判断
// n 当前长度 i 上一次方向 x,y 当前坐标 xnew ynew 新坐标
bool hasBlock(int i, int x, int y, int xnew, int ynew)
{int a;if (i == 1){for (a = x + 1; a <= xnew; ++a)if (map[a + 250][y + 250] == 2)return true;}if (i == 2){for (a = y + 1; a <= ynew; ++a)if (map[x + 250][a + 250] == 2)return true;}if (i == 3){for (a = ynew; a < y; ++a)if (map[x + 250][a + 250] == 2)return true;}if (i == 4){for (a = xnew; a < x; ++a)if (map[a + 250][y + 250] == 2)return true;}return false;
}// n 当前长度 i 上一次方向 x,y 当前坐标
void dfs(int n, int i, int x, int y)
{int a, newi, xnew, ynew;if (x == 0 && y == 0 && n == lineNumMax){for (a = 0; a < lineNumMax; ++a)lintTotal[totalNum][a] = line[a];totalNum++;return;}if (n >= lineNumMax)return;map[x + 250][y + 250] = 1;for (a = 0; a < 2; ++a){newi = truns[i][a];xnew = x + (n + 1) * steps[newi][0];ynew = y + (n + 1) * steps[newi][1];if (map[xnew + 250][ynew + 250] || hasBlock(newi, x, y, xnew, ynew))continue;line[n] = newi;dfs(n + 1, newi, xnew, ynew);}map[x + 250][y + 250] = 0;
}void computed()
{int i, j;int x, y;// 四个方向都走一遍for (i = 1; i < 5; ++i){line[0] = i;x = steps[i][0];y = steps[i][1];if (map[x + 250][y + 250])continue;dfs(1, i, x, y);}
}int main()
{int co, i, j;scanf("%d", &co);while (co--){init();computed();for (i = 0; i < totalNum; ++i){for (j = 0; j < lineNumMax; ++j)printf("%c", num2str[lintTotal[i][j]]);putchar('\n');}printf("Found %d golygon(s).\n\n", totalNum);}return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com