[Aha]解救小哈

2019-11-06 06:28:56

字体：大中小

来源：转载

供稿：网友

题目：见啊哈算法P81页。分析：最常见的DFS配合最短路，熟悉写法。代码：

#include<iostream>#include<cstdio>using namespace std ; int n , m , p , q , min_n =999999;int a[51][51] , book[51][51];void dfs(int x,int y,int step){ int next[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; int tx ,ty ; if(x==p&&y==q){ if(step < min_n){ min_n = step; } return ; } for(int i = 0 ; i <= 3 ; i++){ tx = x + next[i][0]; ty = y + next[i][1]; if(tx<1||tx>n||ty<1||ty>m) continue ;//边界判断 if((book[tx][ty]==0)&&(a[tx][ty]==0)){//判断是否走过或是障碍物 book[tx][ty] = 1 ; dfs(tx,ty,step+1); book[tx][ty] = 0; } } return ;}int main(){ int startx,starty; //读入n和m，行和列 scanf("%d %d",&n,&m); //读入迷宫 for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= m ;j++) scanf("%d",&a[i][j]); } //读入起点和终点 scanf("%d %d %d %d",&startx,&starty,&p,&q); //从起点开始搜索 book[startx][starty] = 1 ; //标记起点在路径中，防止后面重复走 dfs(startx,starty,0); PRintf("%d",min_n); return 0 ; }

上一篇：POJ2421 Constructing Roads(最小生成树，Prim)

下一篇：1000. Fibonacci