如何制作flash网站,怎样选择网站服务器,上海开发app,美橙网站维护Promble Description
定义一个二维数组#xff1a;
int maze[5][5] {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,}; 它表示一个迷宫#xff0c;其中的1表示墙壁#xff0c;0表示可以走的路#xff0c;只能横着走或竖着走#xff0c;不能斜…Promble Description
定义一个二维数组
int maze[5][5] {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,}; 它表示一个迷宫其中的1表示墙壁0表示可以走的路只能横着走或竖着走不能斜着走要求编程序找出从左上角到右下角的最短路线。
INPUT
一个5 × 5的二维数组表示一个迷宫。数据保证有唯一解。
OUTPUT
左上角到右下角的最短路径格式如样例所示。
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
问题链接http://poj.org/problem?id3984
问题分析根据DFS算法的思想再建立一个数组储存最少步数所走的路径注意格式逗号后面有个空格
AC代码
#includeiostream
using namespace std;
int m[10][10],lx[100],ly[100],min19999999,vis[30][30],xe[100],ye[100];
//m记录地图ly,lx记录路径
int n[4][2] { {1,0},{0,1},{-1,0},{0,-1} }//4个方向
void DFS(int x, int y, int step)//x,y为当前位置step为走到该位置花的步数
{if (x 4 y 4)//判断是否到达终点{if (step min1){min1 step;//记录最小步数for (int i 0; i step; i){xe[i] lx[i];//记录所走的路径ye[i] ly[i];}}return;}for (int i 0; i 4; i)//从4个方向探索{int tx x n[i][0];int ty y n[i][1];if (tx 0 || ty 0 || tx4 || ty4)continue;//判断是否越界if (m[tx][ty] 0 vis[tx][ty] 0)//判断是否访问过能不能走{lx[step] tx;//记录路径ly[step] ty;vis[tx][ty] 1;//标记访问DFS(tx, ty, step 1);//探索下一步步数加一vis[tx][ty] 0;//回溯取消标记}}
}
int main()
{for (int i 0; i 5; i)for (int j 0; j 5; j)cin m[i][j];DFS(0, 0, 0);printf((0, 0)\n);for (int i 0; i min1; i){printf((%d, %d), xe[i], ye[i]);if (i min1 - 1)printf(\n);}
}
转发DFS算法博客链接https://www.cnblogs.com/OctoptusLian/p/7429645.html
