大佬们,为何不直接把走过的格子标记成障碍物啊,wa了三个点
  • 板块P1605 迷宫
  • 楼主ljx_gkx
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/3/29 22:21
  • 上次更新2023/10/23 20:04:26
查看原帖
大佬们,为何不直接把走过的格子标记成障碍物啊,wa了三个点
853953
ljx_gkx楼主2023/3/29 22:21
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 6;
int n, m, t;
int sx, sy, fx, fy;
bool obs[N][N];
int cnt;
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)
    {
        cnt ++;
        return;
    }
    
    for (int i=0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > m || obs[a][b]) continue;
        obs[a][b] = true;
        dfs (a, b);
        obs[a][b] = false;
    }
}

int main()
{
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;
    memset (obs, false, sizeof(obs));
    
    while (t --)
    {
        int a, b;
        cin >> a >> b;
        obs[a][b] = true;
    }
    dfs (sx, sy);
    cout << cnt << endl;
    return 0;
}
2023/3/29 22:21
加载中...