POJ3984迷宫问题BFS

    技术2022-05-13  2

    Problem Address:http://poj.org/problem?id=3984

     

    求迷宫的最短路径。

     

    本来是打算试一下怎么求迷宫的,结果最后做出来了。

     

    BFS搜索,同时记录到达每一步的最小步数。

     

    输出路径时则向前递归。

     

    一次RTE后改大数组,然后AC。然后就不改了,直接保存……

     

    如此凌乱的代码啊……不堪入目啊……

     

    也正是由于如此凌乱、如此长的代码,结果在Best solutions of Problem 3984中排到了第一页……

     

    等以后需要的时候重新写一份好的BFS求迷宫最短路径。

     

    以下贴上凌乱的代码:

     

    #include <iostream> using namespace std; int maze[10][10]; struct point { int i; int j; int index; }; void showpath(int i, int j) { int ti,tj; int min=maze[i][j]; if (i-1>=0) { if (maze[i-1][j]>1 && maze[i-1][j]<min) { ti = i-1; tj = j; min = maze[ti][tj]; } } if (i+1<5) { if (maze[i+1][j]>1 && maze[i+1][j]<min) { ti = i+1; tj = j; min = maze[ti][tj]; } } if (j-1>=0) { if (maze[i][j-1]>1 && maze[i][j-1]<min) { ti = i; tj = j-1; min = maze[ti][tj]; } } if (j+1<5) { if (maze[i][j+1]>1 && maze[i][j+1]<min) { ti = i; tj = j+1; min = maze[ti][tj]; } } if (min!=maze[i][j]) { showpath(ti,tj); } printf("(%d, %d)/n", i, j); } int main() { int i,j,index; int s,t; point p[100]; for (i=0; i<5; i++) { for (j=0; j<5; j++) scanf("%d", &maze[i][j]); } s = 0; t = 1; p[0].i = 0; p[0].j = 0; p[0].index = 2; maze[0][0] = 2; index = 2; while(t>s) { i = p[s].i; j = p[s].j; index=p[s].index+1; s++; if (i+1<5) { if (maze[i+1][j]==0) { p[t].i = i+1; p[t].j = j; p[t].index = index; maze[i+1][j] = index; t++; } } if (j+1<5) { if (maze[i][j+1]==0) { p[t].i = i; p[t].j = j+1; p[t].index = index; maze[i][j+1] = index; t++; } } if (i-1>=0) { if (maze[i-1][j]==0) { p[t].i = i-1; p[t].j = j; p[t].index = index; maze[i-1][j] = index; t++; } } if (j-1>=0) { if (maze[i][j-1]==0) { p[t].i = i; p[t].j = j-1; p[t].index = index; maze[i][j-1] = index; t++; } } } showpath(4,4); return 0; }


    最新回复(0)