原题链接:https://www.luogu.com.cn/problem/P1605
题意解读:从起点走到终点的方案数,DFS可遍历所有情况。
解题思路:
在DFS过程中,有两种标记
墙:不能访问
已访问过的,不能重复访问
定义数组int a[N][N]表示迷宫,1是墙或者已访问过的,0是可以通过的。
100分代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int a[N][N];
int n, m, t;
int sx, sy, fx, fy;
int x, y;
long long ans;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y)
{
if(x == fx && y == fy)
{
ans++;
return;
}
for(int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if(a[nx][ny] == 0 && nx >= 1 && nx <= n && ny >= 1 && ny <= m)
{
a[x][y] = 1; //这里要特别注意,要对x、y进行已访问标记
dfs(nx, ny);
a[x][y] = 0; //恢复以回溯
}
}
}
int main()
{
cin >> n >> m >> t;
cin >> sx >> sy >> fx >> fy;
while(t--)
{
cin >> x >> y;
a[x][y] = 1;
}
dfs(sx, sy);
cout << ans;
return 0;
}
标签:int,洛谷题,迷宫,nx,ny,&&,fy,P1605 From: https://www.cnblogs.com/jcwy/p/18056765