题解 P1605 【迷宫】

Lngstart

2019-07-14 10:37:13

Solution

整体来说这道题目比较的简单,是比较基础的搜索题 ------------ 思路就是从起点开始采用dfs的思想,一直向下搜索,一旦遇到目标点就记为+1次 ------------ 代码如下: ------------ ```cpp #include<iostream> using namespace std; int a[6][6];//用来储存地图和标记作用 int next[4][2]={{1, 0}, {-1, 0},{0, 1},{0, -1}};//方向数组 int sx, sy, fx, fy;//代表了起点和终点的坐标 int m, n, t;//m代表行,n代表列,t代表障碍数 int ans = 0;//总的条数 void dfs(int sx, int sy){ int nx, ny; if(sx == fx && sy == fy){//终点的判定条件 ans++; return; } a[sx][sy] = 1;//走过的要进行标记 for(int i = 0; i < 4; ++i){//枚举上下左右四个方向 nx = sx + next[i][0]; ny = sy + next[i][1]; if(nx < 1 || nx > m || ny < 1 || ny > n)//边界的判定条件 continue; if(a[nx][ny] == 0){ a[nx][ny] = 1; dfs(nx,ny); a[nx][ny] = 0; } } } int main(){ cin >> m >> n >> t; cin >> sx >> sy >> fx >> fy; int x, y; for(int i = 0; i < t; ++i){ cin >> x >> y; a[x][y]=1;//标记障碍的位置 } dfs(sx,sy); cout << ans << endl; return 0; } ``` ~~第一次发题解,望管理员通过^_^~~