住房和城乡建设部网站建筑合同,jsp在网站开发中的优势,海口网站建设方案,建设微信网站连通块记忆性递归的综合运用
这里x#xff0c;y的设置反我平常的习惯#xff0c;搞得我有点晕
实际上可以一输入就交换x#xff0c;y的数据的
如果设置y1为全局变量的话会warning#xff1a;
warning: built-in function y1 declared as non-function
所以我改成p和q了…
连通块记忆性递归的综合运用
这里xy的设置反我平常的习惯搞得我有点晕
实际上可以一输入就交换xy的数据的
如果设置y1为全局变量的话会warning
warning: built-in function y1 declared as non-function
所以我改成p和q了
刚开始判断能不能相连是靠连通块
后面求最短线段数是靠记忆性递归 代码如下
#includestdio.h
struct Min{int x_d;//x轴的方向int y_d;//y轴的方向int len;
}min[77][77];
void fill(int color, int x, int y);
bool judge(int m1, int n1, int m2, int n2);
void dg(int y, int x, int color, int y_d, int x_d);
int map[77][77];
int w, h, p1, q1, p2, q2;int main(void)
{//板子输入scanf(%d%d, w, h);getchar();for(int i 1; i h; i){char c;for(int j 1; j w; j)if((c getchar()) X)map[i][j] 1;elsemap[i][j] 0;getchar();}//开始填充连通块int color 2;fill(color, 0, 0);for(int i 1; i h; i)for(int j 1; j w; j)if(map[i][j] 0)fill(color, i, j);//开始判断并计算int n;scanf(%d, n);for(int i 0; i n; i){scanf(%d%d%d%d, p1, q1, p2, q2);if(judge(p1, q1, p2, q2)){printf(impossible\n);continue;}//重置min数组for(int i 0; i h 1; i)for(int j 0; j w 1; j)min[i][j].len 100, min[i][j].x_d 0, min[i][j].y_d 0;min[q1][p1].len 0;//求最短线段数从x1y1到x2y2if(map[q1 1][p1] ! 1) dg(q1 1, p1, map[q1 1][p1], 1, 0);if(map[q1 - 1][p1] ! 1) dg(q1 - 1, p1, map[q1 - 1][p1], -1, 0);if(map[q1][p1 1] ! 1) dg(q1, p1 1, map[q1][p1 1], 0, 1);if(map[q1][p1 - 1] ! 1) dg(q1, p1 - 1, map[q1][p1 - 1], 0, -1);//得到最短线段数int minn 100;if(map[q2 1][p2] ! 1){int tmp min[q2 1][p2].len ((min[q2 1][p2].x_d 0 min[q2 1][p2].y_d -1) ? 0 : 1);minn (minn tmp) ? minn : tmp;}if(map[q2 - 1][p2] ! 1){int tmp min[q2 - 1][p2].len ((min[q2 - 1][p2].x_d 0 min[q2 - 1][p2].y_d 1) ? 0 : 1);minn (minn tmp) ? minn : tmp;}if(map[q2][p2 1] ! 1){int tmp min[q2][p2 1].len ((min[q2][p2 1].x_d -1 min[q2][p2 1].y_d 0) ? 0 : 1);minn (minn tmp) ? minn : tmp;}if(map[q2][p2 - 1] ! 1){int tmp min[q2][p2 - 1].len ((min[q2][p2 - 1].x_d 1 min[q2][p2 - 1].y_d 0) ? 0 : 1);minn (minn tmp) ? minn : tmp;}//输出if(minn 10) printf(impossible\n);else printf(%d\n, minn);}return 0;
}
void fill(int color, int x, int y)
{if(map[x][y]) return;if(x 0 || y 0 || x h 1 || y w 1) return;map[x][y] color;fill(color, x 1, y), fill(color, x - 1, y);fill(color, x, y 1), fill(color, x, y - 1);return;
}
bool judge(int m1, int n1, int m2, int n2)
{int tmp1[4] {map[n1 1][m1], map[n1 - 1][m1], map[n1][m1 1], map[n1][m1 - 1]};int tmp2[4] {map[n2 1][m2], map[n2 - 1][m2], map[n2][m2 1], map[n2][m2 - 1]};for(int i 0; i 4; i){if(tmp1[i] 1) continue;for(int j 0; j 4; j){if(tmp2[j] 1) continue;if(tmp1[i] tmp2[j]) return false;}}return true;//只是代表是否执行if而不是能不能连通
}
void dg(int y, int x, int color, int y_d, int x_d)
{if(x 0 || y 0 || x w 1 || y h 1) return;if(map[y][x] ! color) return;int tmp min[y - y_d][x - x_d].len ((x_d min[y - y_d][x - x_d].x_d y_d min[y - y_d][x - x_d].y_d) ? 0 : 1);if(tmp min[y][x].len) return;//等于的话不用返回min[y][x].len tmp, min[y][x].x_d x_d, min[y][x].y_d y_d;dg(y 1, x, color, 1, 0);dg(y - 1, x, color, -1, 0);dg(y, x 1, color, 0, 1);dg(y, x - 1, color, 0, -1);return;
}
这里实际上可以改一下目的地的color本来是1使旁边的块可以直接走到目的地而不是目的地旁边
只要在4个方向的递归开始的时候改成相应的颜色就可以了记得改回来以后还要用
这样就不会显得累赘可以把求最短线段数部分和得到最短线段数部分合并代码会更短一点
懒得改了
