huanghai
/
python
1
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'main'
${ noResults }
python/C++专题课程/回溯算法/迷宫/C++ 用回溯法求解迷宫问题（递归）.cpp

104 lines
2.7 KiB
Raw Permalink Normal View History Unescape

'commit'
2 years ago
#include <bits/stdc++.h>
using namespace std;
/*
һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>壺
<EFBFBD><EFBFBD><EFBFBD>ݷ<EFBFBD><EFBFBD><EFBFBD>̽<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݷ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD>ѡ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֳ<EFBFBD>Ϊ<EFBFBD><EFBFBD>̽<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѡ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǰ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԴﵽĿ<EFBFBD>ꡣ
<EFBFBD><EFBFBD><EFBFBD><EFBFBD>̽<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ijһ<EFBFBD><EFBFBD>ʱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԭ<EFBFBD><EFBFBD>ѡ<EFBFBD>񲢲<EFBFBD><EFBFBD>Ż<EFBFBD><EFBFBD>ﲻ<EFBFBD><EFBFBD>Ŀ<EFBFBD>꣬<EFBFBD><EFBFBD><EFBFBD>˻<EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ѡ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>߲<EFBFBD>ͨ<EFBFBD><EFBFBD>
<EFBFBD>˻<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ߵļ<EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><EFBFBD><EFBFBD>ݷ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ij<EFBFBD><EFBFBD>״̬<EFBFBD>ĵ<EFBFBD><EFBFBD><EFBFBD>Ϊ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݵ㡱<EFBFBD><EFBFBD>
<EFBFBD>û<EFBFBD><EFBFBD>ݷ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʱ<EFBFBD><EFBFBD>ʹ<EFBFBD>õݹ鷽<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>̽<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʹ<EFBFBD><EFBFBD>ջ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǰ<EFBFBD><EFBFBD>̽<EFBFBD>ͻ<EFBFBD><EFBFBD>ݡ<EFBFBD>
<EFBFBD><EFBFBD><EFBFBD><EFBFBD>˼·<EFBFBD><EFBFBD>
1.<EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ά<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʾ<EFBFBD>Թ<EFBFBD><EFBFBD><EFBFBD>
<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>е<EFBFBD>ֵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>1<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʾ<EFBFBD><EFBFBD>λ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ǽ<EFBFBD>ڣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͨ<EFBFBD>У<EFBFBD>
<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>0<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʾ<EFBFBD><EFBFBD>λ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͨ·<EFBFBD><EFBFBD>
<EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>飬<EFBFBD><EFBFBD><EFBFBD>Ǹ<EFBFBD>λ<EFBFBD><EFBFBD><EFBFBD>Ƿ񱻷<EFBFBD><EFBFBD>ʹ<EFBFBD><EFBFBD><EFBFBD>
2.<EFBFBD>Թ<EFBFBD>ǰ<EFBFBD><EFBFBD><EFBFBD>ķ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD>ṹ<EFBFBD><EFBFBD><EFBFBD>洢<EFBFBD><EFBFBD><EFBFBD><EFBFBD>
<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>8<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>򣺶<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϣ<EFBFBD><EFBFBD>ϣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
3.<EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ںͳ<EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>꣬<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>֣<EFBFBD>
ѭ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>8<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><EFBFBD>ͨ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݹ<EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD>ã<EFBFBD>һֱ<EFBFBD>ݹ<EFBFBD><EFBFBD><EFBFBD>ȥ<EFBFBD><EFBFBD>ֱ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڻ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>з<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>·<EFBFBD><EFBFBD>ͨ<EFBFBD><EFBFBD><EFBFBD>ݣ<EFBFBD>
*/
// Ĭ<><C4AC><EFBFBD>Թ<EFBFBD><D4B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
const int XLEN = 14, YLEN = 17;
int m, p; // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
int maze[XLEN + 2][YLEN + 2]; // <20>Թ<EFBFBD><D4B9><EFBFBD><EFBFBD><EFBFBD>
int mark[XLEN + 2][YLEN + 2]; // <20><><EFBFBD>ʱ<EFBFBD><CAB1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// <20><><EFBFBD><EFBFBD><EFBFBD>壬<EFBFBD><E5A3AC><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD>ά<EFBFBD><CEAC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA>,a<><61>b<EFBFBD><62>x,y<><79><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƫ<EFBFBD><C6AB>
struct Offsets {
int a, b;
};
// <20><>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD>Ҫ<EFBFBD><D2AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>԰ѷ<D4B0><D1B7><EFBFBD>ȥ<EFBFBD><C8A5>
Offsets direction[8] =
{{-1, 0},
{-1, 1},
{0, 1},
{1, 1},
{1, 0},
{1, -1},
{0, -1},
{-1, -1}
};
// <20><><EFBFBD><EFBFBD><EFBFBD>Թ<EFBFBD><D4B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĵݹ<C4B5><DDB9>㷨
bool seekPath(int x, int y) {
// <20><><EFBFBD>Թ<EFBFBD>ijһλ<D2BB><CEBB>[i][j]<5D><>ʼ<EFBFBD><CABC>Ѱ<EFBFBD>ҳ<EFBFBD><D2B3><EFBFBD>[m][p]<5D><>һ<EFBFBD><D2BB>·<EFBFBD><C2B7>,<2C><><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>true
int i, g, h; // g, h<><68>¼λ<C2BC><CEBB><EFBFBD><EFBFBD>Ϣ
if (x == m && y == p) // m<><6D>p<EFBFBD>dz<EFBFBD><C7B3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
return true;
// ѭ<><D1AD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>(x, y)<29><>8<EFBFBD><38><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
for (i = 0; i < 8; i++) {
g = x + direction[i].a;
h = y + direction[i].b;
// <20><><EFBFBD><EFBFBD>һλ<D2BB><CEBB>Ѱ<EFBFBD><D1B0>ͨ<EFBFBD><CDA8><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>·<EFBFBD><C2B7>
if (maze[g][h] == 0 && mark[g][h] == 0) { // <20><><EFBFBD><EFBFBD>ͨ<EFBFBD><CDA8>δ<EFBFBD><CEB4><EFBFBD><EFBFBD><EFBFBD>ʹ<EFBFBD>
mark[g][h] = 1; // <20><><EFBFBD><EFBFBD>Ϊ<EFBFBD>ѷ<EFBFBD><D1B7>ʹ<EFBFBD>
if (seekPath(g, h)) { // <20>ݹ<EFBFBD><DDB9><EFBFBD>̽
cout << "(" << g << ", " << h << ")<29><>"; // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>·<EFBFBD><C2B7><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
return true;
}
}
// <20><><EFBFBD>ݣ<EFBFBD><DDA3><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>̽ͨ<CCBD><CDA8><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>·<EFBFBD><C2B7>
}
return false; // <20>Ҳ<EFBFBD><D2B2><EFBFBD>ͨ<EFBFBD><CDA8><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>·<EFBFBD><C2B7>
}
int main(int argc, const char *argv[]) {
//<2F><>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD>
freopen("./data.txt", "r", stdin);
int i, j, x, y;
// <20><><EFBFBD><EFBFBD><EFBFBD>Թ<EFBFBD><D4B9><EFBFBD><EFBFBD><EFBFBD>
for (i = 0; i < XLEN; i++) {
for (j = 0; j < YLEN; j++) {
cin >> maze[i][j];
//<2F><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
mark[i][j] = 0;
}
}
//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
cin >> x >> y;
//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
cin >> m >> p;
// <20><><EFBFBD><EFBFBD><EFBFBD>ڿ<EFBFBD>ʼ
mark[x][y] = 1;
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Թ<EFBFBD><D4B9>ĵݹ<C4B5><DDB9>㷨
if (seekPath(x, y)) // <20>ɹ<EFBFBD>
{
cout << "(" << x << ", " << y << ")" << endl;
} else {
cout << "<EFBFBD>Ҳ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD>·<EFBFBD><EFBFBD><EFBFBD><EFBFBD>" << endl;
}
return 0;
}