poj3984
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~
版权声明：本文为gerjcs原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。