解题思路:DFS深搜 + 剪枝
注意事项:移动的顺序, 下右上左
参考代码:
#include<iostream> #include<string> #include<sstream> #include<cstring> using namespace std; const int N = 1e1 + 10; int g[N][N],dis[N][N],mx= 0x3f3f3f3f; int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; bool v[N][N]; string m_path; void dfs(int x, int y, string path, int lth){ if(x == 4 && y == 4){ if(mx > lth) { m_path = path; mx = lth; } return; } if(dis[x][y] > lth) dis[x][y] = lth; else return; for(int i = 0 ; i < 4; i ++){ int nx = d[i][0] + x; int ny = d[i][1] + y; if(nx >= 0 && nx < 5 && ny >=0 && ny < 5 && !g[nx][ny] && !v[nx][ny]){ v[nx][ny] = true; stringstream ss; ss << path << "\n(" <<nx <<", "<<ny<<")"; dfs(nx,ny,ss.str(),lth + 1); v[nx][ny] = false; } } } int main() { memset(dis, 0x3f, sizeof(dis)); for(int i = 0; i < 5; i ++) for(int j = 0; j < 5; j ++) cin >> g[i][j]; string s = "(0, 0)"; dfs(0,0,s,0); cout << m_path; return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题6.5 (Java代码)浏览:1124 |
C语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:794 |
多输入输出练习1 (C语言代码)浏览:1189 |
DNA (C语言代码)浏览:540 |
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:514 |
图形输出 (C语言代码)浏览:1387 |
Tom数 (C语言代码)浏览:527 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:471 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:527 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:646 |