POJ 3984 迷宫问题【DFS】

2019-11-08 03:22:05

字体：大中小

来源：转载

供稿：网友

题目链接：http://poj.org/PRoblem?id=3984 题意：中文题…… 解析：图不大，dfs直接做，到终点时更新下路径就好

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <queue>using namespace std;const int inf = 0x7fffffff;int minn = inf;int a[25][25];int vis[25][25];int ans[25][25];int dx[] = {0,1,-1,0};int dy[] = {1,0,0,1};void dfs(int x,int y,int step){ if(x==4 && y==4) { if(step<minn) { minn = step; for(int i=0;i<5;i++) { for(int j=0;j<5;j++) ans[i][j] = vis[i][j]; } } } for(int i=0;i<4;i++) { int tx = dx[i]+x; int ty = dy[i]+y; if(vis[tx][ty] || tx<0 || tx>4 || ty<0 ||ty>4) continue; if(a[tx][ty]==1) continue; vis[tx][ty] = vis[x][y]+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++) scanf("%d",&a[i][j]); memset(vis,0,sizeof(vis)); minn = inf; vis[0][0] = 1; dfs(0,0,0); for(int i=0;i<5;i++) { for(int j=0;j<5;j++) { if(ans[i][j]) printf("(%d, %d)/n",i,j); } } return 0;}

上一篇：时间序列分析（1）R语言-计算简单收益率

下一篇：抽象建模