本文共 1368 字,大约阅读时间需要 4 分钟。
这道题题意还是需要仔细去理解的。
1.虽然求最短路径,但是这道题用广搜很难实现,因为棋盘在改变。题目有说steps要小于10也在提示用深搜,已经给了剪枝。 2.这道题太多细节,每次撞击才算是一次相邻的元素访问。起步的时候不能直接撞障碍物,~~~。void dfs(int x, int y){ if (steps == 10) return; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (a[nx][ny] == 1)continue;//起步直接撞击 while (nx >= 0 && nx < M&&ny >= 0 && ny < N&&a[nx][ny] == 0) { nx += dx[i]; ny += dy[i]; } if (nx >= 0 && nx < M&&ny >= 0 && ny < N) { if (a[nx][ny] == 3) { steps++; if (Min > steps)Min = steps; steps--;//回溯去找更小的 return; } if (a[nx][ny] == 1) { a[nx][ny] = 0; steps++; dfs(nx - dx[i], ny - dy[i]); a[nx][ny] = 1;//回溯 steps--;//回溯 } } }}int main(){ int gx, gy; while (cin >> N >> M, N || M) { for(int i=0;i> a[i][j]; if (a[i][j] == 2) { sx = i; sy = j; a[i][j] = 0; } } Min = INT_MAX; steps = 0; dfs(sx, sy); if (Min == INT_MAX) cout << -1 << endl; else cout << Min << endl; } system("pause");}
转载地址:http://mzyci.baihongyu.com/