poj 3009 dfs

xiaoxiao2021-02-28  70

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> using namespace std; const int maxn = 25; const int inf = 0x3f3f3f3f; int n,m; int mark[maxn][maxn]; int sx, sy; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int ans = inf; void dfs(int x, int y, int dep) { if (dep >= 10){ return; } if (dep >= ans){ return; } for (int k = 0; k < 4; k++){ int i = x, j = y; int cnt = 0; while (1){ i += dx[k]; j += dy[k]; if (i >= n || i < 0 || j >= m || j < 0){ cnt = 0; break; } if (mark[i][j] == 1){ break; } if (mark[i][j] == 3){ ans = min(ans, dep + 1); return; } cnt++; } if (cnt == 0){ continue; } mark[i][j] = 0; dfs(x + cnt * dx[k], y + cnt * dy[k], dep + 1); mark[i][j] = 1; } } int main(){ while(cin>>m>>n && n && m){ ans = inf; for (int i = 0; i < n; i++){ for (int j=0;j<m;j++){ cin>>mark[i][j]; if (mark[i][j] == 2){ sx = i; sy = j; } } } dfs(sx, sy, 0); if (ans == inf){ cout << "-1" << endl; } else{ cout << ans << endl; } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-81438.html

最新回复(0)