ACM 训练日志记录 · 思考 · 成长 提交 / 修改记录
廖夏 / 题目列表训练档案
导出

P1605 迷宫

来源:洛谷 ★ 1000

搜索递推枚举自评已掌握
本题活力0.38按难度、完成结果与训练证据估算

算法如山行则将至

题目描述

迷宫

题目描述

给定一个 $N \times M$ 方格的迷宫,迷宫里有 $T$ 处障碍,障碍处不可通过。

在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标,每个方格最多经过一次,问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 $N,M,T$,分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 $SX,SY,FX,FY$。$SX,SY$ 代表起点坐标,$FX,FY$ 代表终点坐标。

接下来 $T$ 行,每行两个正整数,表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

说明/提示

对于 $100\%$ 的数据,$1 \le N,M \le 5$,$1 \le T \le 10$,$1 \le SX,FX \le N$,$1 \le SY,FY \le M$。

样例 1

输入:

2 2 1
1 1 2 2
1 2

输出:

1

代码

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 10;
//int is_ob[MAXN][MAXN];
int vis[MAXN][MAXN];
int sx, sy;
int fx, fy;
int n, m, t;
int ans;
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
void dfs(int cx, int cy){
//	printf("%d %d\n", cx, cy);
	if (cx == fx && cy == fy) {ans++; return;}
	for (int i = 0; i < 4; i++){
		int x = cx + dx[i];
		int y = cy + dy[i];
		if (x >= 1 && y >= 1 && x <= m && y <= n && !vis[x][y] /*&& !is_ob[x][y]*/){
			vis[x][y] = 1;
			dfs(x, y);
			vis[x][y] = 0;
		}
	}
}
int main(){
	cin >> n >> m >> t;
	cin >> sx >> sy >> fx >> fy;
	for (int i = 1; i <= t; i++) {
		int x, y;
		cin >> x >> y;
		vis[x][y] = 1;
	}
	vis[sx][sy] = 1;
//	is_ob[sx][sy] = 1;
	dfs(sx, sy);
	cout << ans;
	return 0;
}



/****下面的是AI代码********************/
#include <iostream>
#include <queue>
using namespace std;

int n, m, t;
int sx, sy, fx, fy;

bool obstacle[6][6];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct State {
    int x, y;
    long long vis;
};

int id(int x, int y) {
    return (x - 1) * m + (y - 1);
}

int main() {
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;

    for (int i = 0; i < t; i++) {
        int x, y;
        cin >> x >> y;
        obstacle[x][y] = true;
    }

    queue<State> q;

    long long startMask = 1LL << id(sx, sy);
    q.push({sx, sy, startMask});

    int ans = 0;

    while (!q.empty()) {
        State u = q.front();
        q.pop();

        if (u.x == fx && u.y == fy) {
            ans++;
            continue;
        }

        for (int i = 0; i < 4; i++) {
            int x = u.x + dx[i];
            int y = u.y + dy[i];

            if (x < 1 || x > n || y < 1 || y > m)
                continue;

            if (obstacle[x][y])
                continue;

            int p = id(x, y);

            if (u.vis & (1LL << p))
                continue;

            q.push({
                x,
                y,
                u.vis | (1LL << p)
            });
        }
    }

    cout << ans;
}