寒假所学算法复习3月12
3月12复习了深度优先搜索(dfs)和广度优先搜索(bfs)
刷了洛谷上的一道题:[POI2007]GRZ-Ridges and Valleys - 洛谷
原本想用dfs写,但写到一半,发现思路不对,于是又用bfs去写,思路如下:
地图上有三种区域,山峰,山谷,山坡,当一个相同数的区域的周围全是比这个数要小的数这个区域就是山峰,否则就是山谷,但只要有周围的一个数不是比他小或是比他大,则这个区域是山坡,于是只要一个区域一个区域的搜索,就可以统计出整个地图的各种地形的数量,关键在于对每个区域的搜索,我用的是bfs去搜,由于地图较小,数据结构用的是邻接矩阵来存图,用两个变量标记这个区域边缘的数相对于该区域的数的大小,搜完之后通过这两个标记就可以判断这个区域的地形类型,最后统计输出即可,代码如下:
-
-
-
int maps[size][size];
-
bool vismap[size][size] = {0};
-
int all1 = 0, all2 = 0, n;
-
int directx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, directy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
-
struct fkl {
-
int first;
-
int x, y;
-
} stack[1000007];
-
int main() {
-
int n;
-
scanf("%d", &n);
-
for (int i = 1; i <= n; i ) {
-
for (int p = 1; p <= n; p ) {
-
scanf("%d", &maps[i][p]);
-
}
-
}
-
for (int i = 1; i <= n; i ) {
-
for (int p = 1; p <= n; p ) {
-
if (vismap[i][p] == true) {
-
continue;
-
}
-
int morebig = 0, moresmall = 0;
-
int head = 0, tail = 0;
-
stack[tail].first = maps[i][p];
-
stack[tail].x = i;
-
stack[tail].y = p;
-
tail ;
-
while (head < tail) {
-
int tx = stack[head].x, ty = stack[head].y, tf = stack[head].first;
-
head ;
-
for (int pi = 0; pi < 8; pi ) {
-
int nx = tx directx[pi], ny = ty directy[pi];
-
if ( nx <= 0 || nx > n || ny <= 0 || ny > n) {
-
continue;
-
}
-
if (maps[nx][ny] != tf) {
-
if (maps[nx][ny] < tf) {//峰
-
moresmall ;
-
} else {
-
morebig ;
-
}
-
continue;
-
}
-
if (vismap[nx][ny] == true) {
-
continue;
-
}
-
vismap[nx][ny] = true;
-
stack[tail].first = tf;
-
stack[tail].x = nx;
-
stack[tail].y = ny;
-
tail ;
-
}
-
}
-
if (moresmall == 0) { //山谷
-
all2 ;
-
}
-
if (morebig == 0) {
-
all1 ;
-
}
-
}
-
}
-
printf("%d %d", all1, all2);
-
}
既然用bfs的思路出来了,那么dfs的思路不就也出来了吗,于是顺便又用dfs写了一次
-
-
-
int maps[size][size];
-
bool vismap[size][size] = {0};
-
int all1 = 0, all2 = 0, n;
-
int morebig = 0, moresmall = 0;
-
int directx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, directy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
-
void dfs(int x, int y, int first) {
-
for (int i = 0; i < 8; i ) {
-
int nx = x directx[i], ny = y directy[i];
-
if ( nx <= 0 || nx > n || ny <= 0 || ny > n) {
-
continue;
-
}
-
if (maps[nx][ny] != first) {
-
if (maps[nx][ny] < first) {//峰
-
moresmall ;
-
} else {
-
morebig ;
-
}
-
continue;
-
}
-
if (vismap[nx][ny] == true) {
-
continue;
-
}
-
vismap[nx][ny] = true;
-
dfs(nx, ny, first);
-
}
-
}
-
int main() {
-
scanf("%d", &n);
-
for (int i = 1; i <= n; i ) {
-
for (int p = 1; p <= n; p ) {
-
scanf("%d", &maps[i][p]);
-
}
-
}
-
for (int i = 1; i <= n; i ) {
-
for (int p = 1; p <= n; p ) {
-
if (vismap[i][p] == true) {
-
continue;
-
}
-
morebig = 0, moresmall = 0;
-
vismap[i][p] = true;
-
dfs(i, p, maps[i][p]);
-
//printf("\n%d %d\n\n", morebig, moresmall);
-
if (moresmall == 0) { //山谷
-
all2 ;
-
}
-
if (morebig == 0) {
-
all1 ;
-
}
-
}
-
}
-
printf("%d %d", all1, all2);
-
}
写得比较顺手,再去写一个比较难一点的:刺杀大使 - 洛谷
我最开始的思路:
题目要求:从第一行走到最后一行,每条路线上的最大伤害为这条路的伤害,求所有路线中伤害最小的路线的伤害值,用bfs,用两个标记,一个llmin,一个tllmax,分别用来存储所有路线中伤害最小的路线的伤害值,和某条路线中的个点的伤害的最大值,用bfs边搜索下一个点,边将这个点的伤害值与当前的tllmax比较,取最大的伤害值,当一个路线出来后将这个路线的伤害值与当前的llmin进行比较,取最小的,所有路线搜索完之后llmin及时最终的结果,但我提交上去后发现不仅超时,还有部分测试点错误,先贴上我的错误代码
-
/*
-
5 4
-
0 0 0 0
-
2 5 6 1
-
3 1 6 7
-
9 6 4 8
-
0 0 0 0
-
*/
-
-
-
-
//bfs错误思路
-
-
-
int main() {
-
-
int n, m;
-
int maps[size][size];
-
bool vismap[size][size] = {0};
-
struct direst {
-
int x, y;
-
int onmax;
-
} stack[size * size];
-
scanf("%d %d", &n, &m);
-
for (int i = 1; i <= n; i ) {
-
for (int ip = 1; ip <= m; ip ) {
-
scanf("%d", &maps[i][ip]);
-
}
-
}
-
int llmin = 888888;
-
int diretxy[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
-
-
-
for (int i = 1; i <= m; i ) {
-
int head = 0, tail = 0, tllmax = 888888;
-
memset(vismap, false, sizeof(vismap));
-
stack[tail].x = 2, stack[tail].y = i, stack[tail].onmax = maps[2][i];
-
tail ;
-
while (head < tail) {
-
int tx = stack[head].x, ty = stack[head].y, tmax = stack[head].onmax;
-
head ;
-
for (int p = 0; p < 4; p ) {
-
int nx = tx diretxy[p][0], ny = ty diretxy[p][1];
-
if (nx == n - 1 && tmax > tllmax) {
-
tllmax = tmax;
-
continue;
-
}
-
if (vismap[nx][ny] == true || nx <= 2 || nx >= n - 1 || ny <= 0 || ny > m) {
-
continue;
-
}
-
vismap[nx][ny] = true;
-
stack[tail].x = nx, stack[tail].y = ny;
-
if (tmax < maps[nx][ny]) {
-
tmax = maps[nx][ny];
-
}
-
stack[tail].onmax = tmax;
-
tail ;
-
}
-
}
-
if (tllmax < llmin) {
-
llmin = tllmax;
-
}
-
}
-
printf("%d", llmin);
-
}
害,看了下题解,发现思路错了,决定等以后复习完相关的知识点再来复习
//正确思路:dfs 二分查找
//或是:kruskal 点权转边权
//最大值的最小值:为啥要想到二分
搜索先就此为止吧,打算先复习其他的
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfibjbc
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24