文档章节

poj3984

o
 osc_a22drz29
发布于 2019/03/26 21:22
字数 3163
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

  3/24考完蓝桥杯只做出了1个编程题,4个填空题,能不能省一还不知道,本来是想为了明年二战准备的,希望复试可以多一点加成。

最后一个填空题没有做出来,题目是给你30*50的地图(0/1组成),从(0,0)到(29,49)找出一条最短的路径并且输出路径(按照字典序)。当时没有调试出来,回到学校找到了poj的类似题目a掉了

 

题目链接:http://poj.org/problem?id=3984

题目大意:给你5*5的地图,上下左右,从左上角走到右下角,找出最短路径并且输出这条路径

 

绕了很多弯路,最后总算自己想出来了,很久不摸bds,不看题解,能自己想出来ac还是有点激动的

总结:出错原因

0.要用队列,设一个变量指向头一个指向尾巴

1.走过的要标注不再走了,之前想的是我地图里总有可以到达(4,4)的一条路径,我不用标注到终点了直接break就行,但是实际打印了一下发现不标注会走很多次,很久才到终点,甚至没到终点就return 负数自动结束了,猜测可能爆队列还是什么的

2.我最短路径每次++不知道放在哪里,之前放在了for(0~5)这里,觉得只要for一次就要++,因为以我这个点为中心其他上下左右都要一次入队列,就想for之后++可以记录最短,但是没有想到的是,这是广搜,搜到会跳出打印最短步数,走到非最短路径的那些点去for结束++的时候就多加了步数。正确的记录步数++应该是开一个二维数组,我在上一步的基础上+1,单独计算步数,不会出错。

(观众:你能说点人话嘛,表示听不懂~)

 

以上是考场犯下的错误QAQ~

下面是回到寝室想了一下午想出来的如何记录路径:

我用一个二维数组的结构体(成员为parentX, parentY),每一次记录下他的父亲和上下左右四个(最多)儿子的关系,最后倒着输出从(4,4)往回找

 

注意:

1 t = trackfirst[m][n].parentX;
2 n = trackfirst[m][n].parentY;
3 m = t;

这里之前写的是

1 m = trackfirst[m][n].parentX;
2 n = trackfirst[m][n].parentY;

找了好久Orz,被保研室友lbc回来秒看出错误。

这里结构体设置的收获是看谁多,多的开数组记录,少的作为成员变量,比如这里是儿子多,父亲少,一个父亲对0-4个儿子,所以用数组来存储儿子,用双亲parentX, parentY代表成员。

 

好了重新理一下思路:

好想没什么好说的~

 

PS:用的是队列并且一定要加入标志判断,走过的就不要再走了

草稿代码(ac):

  1 #include<cstdio>
  2 #include<cstring>
  3 struct trackfirst
  4 {
  5     int parentX;
  6     int parentY;
  7 }trackfirst[5][5];//, mmaapp[100000];
  8 
  9 struct d
 10 {
 11     int x;
 12     int y;
 13 }mmaapp[1000000];
 14 int main()
 15 {
 16 
 17     freopen("C:\\Users\\GerJCS岛\\Desktop\\t.txt", "r", stdin);
 18  int minspace;
 19     for(int i = 0; i < 5; i ++)
 20         for(int j = 0; j < 5; j ++){
 21             trackfirst[i][j].parentX = -1;
 22             trackfirst[i][j].parentY = -1;
 23         }
 24     int pose[5][5];
 25 //    int trackfirst;//25个父亲,每个父亲最多5个儿子   //[25][25][25];
 26     int save[500][500];
 27     int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 28     int map[5][5];
 29     int queue[500][500];
 30     memset(save, 0, sizeof(save));
 31     memset(pose, 0, sizeof(pose));
 32     for(int i = 0; i < 5; i ++){
 33         for(int j = 0; j < 5; j ++)
 34             scanf("%d", &map[i][j]);
 35 //        getchar();
 36     }
 37 //    for(int i = 0; i < 5; i ++)
 38 //    {
 39 //        for(int j = 0; j < 5; j ++)
 40 //            printf("%c", map[i][j]);
 41 //        printf("\n");
 42 //    }
 43     int x, y;
 44     int x1, y1;
 45     int q = 0;
 46     int pflag = 0;
 47     queue[q][0] = 0;
 48     queue[q ++][1] = 0;
 49     save[0][0] = 1;
 50     pose[0][0] = 1;
 51     while(pflag <= q)
 52     {
 53 //        q --;
 54         x = queue[pflag][0];
 55         y = queue[pflag][1];
 56 
 57 //        if(x == 4 && y == 4){
 58 //            printf("%d\n", pose[x][y]);
 59 //            break;
 60 //        }
 61 //        printf("TEST\n");
 62         int wp = 0;
 63         for(int i = 0; i < 4; i ++){
 64             x1 = x + dir[i][0];
 65             y1 = y + dir[i][1];
 66             if(x1 >= 0 && x1 < 5 && y1 >= 0 && y1 < 5 && map[x1][y1] == 0 && !save[x1][y1]){
 67                 queue[q][0] = x1;
 68                 queue[q++][1] = y1;
 69                 save[x1][y1] = 1;
 70                 pose[x1][y1] = pose[x][y] + 1;
 71 
 72                 if(i != 0){//上一次直接用数组,造成了重复赋值
 73                     trackfirst[x1][y1].parentX = x;
 74                     trackfirst[x1][y1].parentY = y;
 75                 }
 76 
 77                 if(x1 == 4 && y1 == 4){
 78 //                    printf("#%d#, %d %d %d\n", pose[x1][y1], wp, x, y);
 79 //                    printf("#%d#\n", pose[x1][y1]);
 80                     minspace = pose[x1][y1];
 81                     break;
 82                 }
 83 //                printf("***%d **\n", pose[x1][y1]);
 84             }
 85         }
 86 //        ans ++;
 87         pflag ++;
 88     }
 89     int m = 4;
 90     int n = 4;
 91 
 92    /*
 93     printf("(4, 4)\n");
 94 //    printf("(2, 4)的父亲是:%d %d\n", trackfirst[2][4].parentX, trackfirst[2][4].parentY);
 95 //    printf("(0, 0)的父亲是:%d %d\n", trackfirst[0][0].parentX, trackfirst[0][0].parentY);
 96 ////    while(trackfirst[m][n].parentX != -1 && trackfirst[m][n].parentY != -1){
 97     while(1){
 98         printf("(%d, %d)\n", trackfirst[m][n].parentX, trackfirst[m][n].parentY);
 99         m = trackfirst[m][n].parentX;
100         n = trackfirst[m][n].parentY;
101         if(m == 0 && n == 0)
102             break;
103         if(m == -1 && n == -1)
104             break;
105         if(m == 1 && n == 0 || m == 4 && n == 3)
106             break;
107     }
108     printf("(0, 0)\n");
109 
110     这部分偏分,找到了父亲但是根本输不出来
111 
112     */
113     int t;
114 //    printf("(4, 4)\n");
115 //    printf("(4, 4)的父亲是:%d %d\n", trackfirst[4][4].parentX, trackfirst[4][4].parentY);
116 //    printf("(3, 4)的父亲是:%d %d\n", trackfirst[3][4].parentX, trackfirst[3][4].parentY);
117 //    printf("(2, 4)的父亲是:%d %d\n", trackfirst[2][4].parentX, trackfirst[2][4].parentY);
118 //    printf("(2, 3)的父亲是:%d %d\n", trackfirst[2][3].parentX, trackfirst[2][3].parentY);
119 //    printf("(2, 2)的父亲是:%d %d\n", trackfirst[2][2].parentX, trackfirst[2][2].parentY);
120 //    printf("(2, 1)的父亲是:%d %d\n", trackfirst[2][1].parentX, trackfirst[2][1].parentY);
121 //    printf("(2, 0)的父亲是:%d %d\n", trackfirst[2][0].parentX, trackfirst[2][0].parentY);
122 //    printf("(1, 0)的父亲是:%d %d\n", trackfirst[1][0].parentX, trackfirst[1][0].parentY);
123 //    printf("(0, 0)的父亲是:%d %d\n\n", trackfirst[0][0].parentX, trackfirst[0][0].parentY);
124 ////    while(trackfirst[m][n].parentX != -1 && trackfirst[m][n].parentY != -1){
125     int num = 0;
126     while(1){
127 //        printf("(%d, %d)\n", trackfirst[m][n].parentX, trackfirst[m][n].parentY);
128         mmaapp[num].x = trackfirst[m][n].parentX;
129         mmaapp[num++].y = trackfirst[m][n].parentY;
130         t = trackfirst[m][n].parentX;
131         n = trackfirst[m][n].parentY;
132         m = t;
133         if((m == 0) && (n == 0))
134             break;
135     }
136     for(int i = num - 1; i >= 0; i --){
137         printf("(%d, %d)\n", mmaapp[i].x, mmaapp[i].y);
138     }
139     printf("(4, 4)\n");
140 //    printf("(0, 0)\n");
141 
142 
143 //    printf("%d %d\n", trackfirst[3][0], trackfirst[4][0]);
144 //    printf("%d %d\n", trackfirst[3][0], trackfirst[3][0]);
145 //    int m = 4;
146 //    int n = 4;
147 //    int w = 0;
148 //    while(1){//想法一模一样就是实现太蠢了
149 ////int i = 3;
150 ////int j = 4;
151 //    w = 0;
152 //    for(int i = 0; i < 5; i ++ && !w)
153 //        for(int j = 0; j < 5; j ++ && !w)
154 //            for(int k = 0; k < 5; k ++ && !w){
155 //                if(trackfirst[i][k] == m && trackfirst[j][k] == n){
156 //                    printf("(%d, %d), %d\n", i, j, k);
157 //                    w = 1;
158 //                    m = i;
159 //                    n = j;
160 //                }
161 ////                if(m == 0 && n == 0){
162 ////                    i = 9;
163 ////                    j = 9;
164 ////                    break;
165 ////                }
166 //            }
167 //            if(m == 0 && n == 0)
168 //                    break;
169 //    }
170 }
171 
172 /*
173 01000
174 01010
175 00000
176 01110
177 00010
178 
179 
180 011
181 000
182 110
183 */

 

AC代码:

  1 #include<cstdio>
  2 #include<cstring>
  3 struct trackfirst
  4 {
  5     int parentX;
  6     int parentY;
  7 }trackfirst[5][5];
  8 
  9 struct d
 10 {
 11     int x;
 12     int y;
 13 }mmaapp[1000000];
 14 int main()
 15 {
 16     freopen("C:\\Users\\GerJCS岛\\Desktop\\t.txt", "r", stdin);
 17     int minspace;
 18     for(int i = 0; i < 5; i ++)
 19         for(int j = 0; j < 5; j ++){
 20             trackfirst[i][j].parentX = -1;
 21             trackfirst[i][j].parentY = -1;
 22         }
 23     int pose[5][5];
 24     int save[500][500];
 25     int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 26     int map[5][5];
 27     int queue[500][500];
 28     memset(save, 0, sizeof(save));
 29     memset(pose, 0, sizeof(pose));
 30     for(int i = 0; i < 5; i ++){
 31         for(int j = 0; j < 5; j ++)
 32             scanf("%d", &map[i][j]);
 33     }
 34     int x, y;
 35     int x1, y1;
 36     int q = 0;
 37     int pflag = 0;
 38     queue[q][0] = 0;
 39     queue[q ++][1] = 0;
 40     save[0][0] = 1;
 41     pose[0][0] = 1;
 42     while(pflag <= q)
 43     {
 44         x = queue[pflag][0];
 45         y = queue[pflag][1];
 46         int wp = 0;
 47         for(int i = 0; i < 4; i ++){
 48             x1 = x + dir[i][0];
 49             y1 = y + dir[i][1];
 50             if(x1 >= 0 && x1 < 5 && y1 >= 0 && y1 < 5 && map[x1][y1] == 0 && !save[x1][y1]){
 51                 queue[q][0] = x1;
 52                 queue[q++][1] = y1;
 53                 save[x1][y1] = 1;
 54                 pose[x1][y1] = pose[x][y] + 1;
 55 
 56                 if(i != 0){
 57                     trackfirst[x1][y1].parentX = x;
 58                     trackfirst[x1][y1].parentY = y;
 59                 }
 60 
 61                 if(x1 == 4 && y1 == 4){
 62                     minspace = pose[x1][y1];
 63                     break;
 64                 }
 65                 printf("##%d %d##\n", x1, y1);
 66             }
 67         }
 68         pflag ++;
 69     }
 70     int m = 4;
 71     int n = 4;
 72 
 73     int t;
 74     int num = 0;
 75     while(1){
 76         mmaapp[num].x = trackfirst[m][n].parentX;
 77         mmaapp[num++].y = trackfirst[m][n].parentY;
 78         t = trackfirst[m][n].parentX;
 79         n = trackfirst[m][n].parentY;
 80         m = t;
 81         if((m == 0) && (n == 0))
 82             break;
 83     }
 84     for(int i = num - 1; i >= 0; i --){
 85         printf("(%d, %d)\n", mmaapp[i].x, mmaapp[i].y);
 86     }
 87     printf("(4, 4)\n");
 88 }
 89 
 90 
 91 /*
 92 
 93 0 1 0 0 0
 94 0 1 0 1 0
 95 0 0 0 0 0
 96 0 1 1 1 0
 97 0 0 0 1 0
 98 
 99 0 1 1
100 0 0 0
101 1 1 0
102 
103 */

 

几次WA是因为Google浏览器自动翻译把英文的(4, 4)翻译成了(4,4)丢了空格QAQ~

 

 

****************************更新*******************************

 

参考博客:https://blog.csdn.net/u013480600/article/details/25486071

 结构体:https://baijiahao.baidu.com/s?id=1606137789197451791&wfr=spider&for=pc

 又学了一下队列和栈

IDE中的AC代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define for(i ,a, b) for(int i = a; i < b; i ++)
 7 
 8 using namespace std;
 9 
10 struct Node{
11     int r, c;
12     Node(int r, int c):r(r), c(c){}
13     Node(){}//必须加
14 }parent[100][100];
15 
16 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
17 int main()
18 {
19     freopen("C:\\Users\\GerJCS岛\\Desktop\\t.txt", "r", stdin);
20     int n = 5;
21     int maze[100][100];
22     int step[100][100];
23     int flag[100][100];
24     memset(maze, 0, sizeof(maze));
25     memset(flag, 0, sizeof(flag));
26     memset(step, 0, sizeof(step));
27     memset(parent, -1, sizeof(parent));
28 
29     for(i, 0, n)
30         for(j, 0, n)
31             scanf("%d", &maze[i][j]);
32 
33     queue<Node> Q;
34     while(!Q.empty()) Q.pop();
35     Q.push(Node(0, 0));
36     step[0][0] = 1;
37     flag[0][0] = 1;//一开始忘了
38     while(!Q.empty()){
39         Node node = Q.front(); Q.pop();
40         int r = node.r;
41         int c = node.c;
42         for(i, 0, 4){
43             int nowr = r + dir[i][0];
44             int nowc = c + dir[i][1];
45 //    printf("%d %d\n", parent[0][0].r, parent[0][0].c);
46             if(nowr >= 0 && nowr < 5 && nowc >= 0 && nowc < 5
47                && maze[nowr][nowc] == 0 && !flag[nowr][nowc]){
48                 flag[nowr][nowc] = 1;
49                 step[nowr][nowc] = step[r][c] + 1;
50 //                printf("%d %d %d\n", nowr, nowc, step[nowr][nowc]);
51                 Q.push(Node(nowr, nowc));//不可以写成node
52                 parent[nowr][nowc].r = r;
53                 parent[nowr][nowc].c = c;
54                 if(nowr == 4 && nowc == 4){//这句加不加效果一样???
55 //                    printf("$$%d %d %d$$\n", r, c, step[4][4]);
56                     break;
57                 }
58             }
59         }
60     }
61     stack<Node> S;
62     int r = 4;
63     int c = 4;
64     int t;
65     S.push(Node(4, 4));
66 //    printf("%d %d\n", parent[2][1].r, parent[2][1].c);
67 //    while(parent[r][c].r != -1 && parent[r][c].c != -1){/*之前这里出现了terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc的报错*/
68 //    while(parent[r][c].r != 0 || parent[r][c].c != 0){
69        while(1){
70         S.push(Node(parent[r][c].r, parent[r][c].c));
71 //        printf("%d %d\n", parent[r][c].r, parent[r][c].c);
72         t = parent[r][c].r;
73         c = parent[r][c].c;
74         r = t;
75         if(r == 0 && c == 0)
76             break;
77 //        printf("%d %d %d %d\n", parent[r][c].r, parent[r][c].c, r, c);
78     }
79 //    printf("#%d %d#\n", S.top().r, S.top().c);
80     while(!S.empty()){
81 //        Node node = S.front();
82         Node node = S.top();S.pop();
83         printf("(%d, %d)\n", node.r, node.c);
84     }
85 }

提交AC代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<stack>
 5 #include<algorithm>
 6 #define for(i ,a, b) for(int i = a; i < b; i ++)
 7 using namespace std;
 8 struct Node{
 9     int r, c;
10     Node(int r, int c):r(r), c(c){}
11     Node(){}//必须加
12 }parent[100][100];
13 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
14 int main()
15 {
16     freopen("C:\\Users\\GerJCS岛\\Desktop\\t.txt", "r", stdin);
17     int n = 5;
18     int maze[100][100];
19     int step[100][100];
20     int flag[100][100];
21     memset(maze, 0, sizeof(maze));
22     memset(flag, 0, sizeof(flag));
23     memset(step, 0, sizeof(step));
24     memset(parent, -1, sizeof(parent));
25     for(i, 0, n)
26         for(j, 0, n)
27             scanf("%d", &maze[i][j]);
28     queue<Node> Q;
29     while(!Q.empty()) Q.pop();
30     Q.push(Node(0, 0));
31     step[0][0] = 1;
32     flag[0][0] = 1;//一开始忘了
33     while(!Q.empty()){
34         Node node = Q.front(); Q.pop();
35         int r = node.r;
36         int c = node.c;
37         for(i, 0, 4){
38             int nowr = r + dir[i][0];
39             int nowc = c + dir[i][1];
40             if(nowr >= 0 && nowr < 5 && nowc >= 0 && nowc < 5
41                && maze[nowr][nowc] == 0 && !flag[nowr][nowc]){
42                 flag[nowr][nowc] = 1;
43                 step[nowr][nowc] = step[r][c] + 1;
44                 Q.push(Node(nowr, nowc));//不可以写成node
45                 parent[nowr][nowc].r = r;
46                 parent[nowr][nowc].c = c;
47                 if(nowr == 4 && nowc == 4){//这句加不加效果一样???
48                     break;
49                 }
50             }
51         }
52     }
53     stack<Node> S;
54     int r = 4;
55     int c = 4;
56     int t;
57     S.push(Node(4, 4));
58        while(1){
59         S.push(Node(parent[r][c].r, parent[r][c].c));
60         t = parent[r][c].r;
61         c = parent[r][c].c;
62         r = t;
63         if(r == 0 && c == 0)
64             break;
65     }
66     while(!S.empty()){
67         Node node = S.top();S.pop();
68         printf("(%d, %d)\n", node.r, node.c);
69     }
70 }

 

 代码简洁清爽不少hhh~

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Akka 网络编程-小黄鸡客服

需求分析 程序网络拓扑图 程序框架图 功能实现 YellowChickenServer.scala package com.akka.yellowchicken.serverimport akka.actor.{Actor, ActorRef, ActorSystem, Props}import com.......

hexiaoming123
31分钟前
9
0
此操作无法完成。 再试一次(-22421) - This action could not be completed. Try Again (-22421)

问题: I am trying to upload an Apple TV App to the App Store for testing purposes, but I got the issue: 我正在尝试将Apple TV App上载到App Store以进行测试,但出现了问题: This A......

javail
40分钟前
21
0
vuepress 插件 markdown 拓展

https://github.com/markdown-it/markdown-it-container 插件开发时需要更新md文件, 否则可能因为缓存问题导致看不到新的效果 在md文件中通过使用标记在此处添加其他站点的博客链接, 如果没有...

阿豪boy
46分钟前
25
0
mac 安装 mysql 5.7

卸载以前的版本 brew services listbrew services stop mysql@5.6brew remove mysql@5.6rm -rf /usr/local/var/mysql 安装 brew install mysql@5.7brew services start mysql@5.7 初始......

Anunakee
49分钟前
29
0
Linux下TCP连接断开后不释放的解决办法

问题:在开发测试时发现断开与服务器端口后再次连接时拒绝连接。 分析:服务器上查看端口占用情况,假设端口为8888。 netstat -anp |grep 8888 发现端口8888端口显示被占用(ip为本机ip确定是...

onedotdot
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部