題目鏈接：http://poj.org/PRoblem?id=3984 題意：中文題…… 解析：圖不大，dfs直接做，到終點(diǎn)時(shí)更新下路徑就好
#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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
