我拒绝使用静态数组
  • 板块P1605 迷宫
  • 楼主Ff_c109
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/5/22 16:24
  • 上次更新2023/11/4 22:53:57
查看原帖
我拒绝使用静态数组
123538
Ff_c109楼主2021/5/22 16:24

尝试无视数据规模

//#include "preload.h"
void preload();

int index();

int main() {
	return preload(), index();
}
#include <iostream>
#define int16 short int
#define int64 long long int
int16** Map;
bool** flag;
int sum = 0;
int64 m, n;
int16 mx[] = {1, 0, -1, 0};
int16 my[] = {0, 1, 0, -1};
int64 Ending[2];

using namespace std;

void preload() {
	cin >> n >> m;
	int16** map;
	map = new int16*[m + 010];
	for(int i = 0; i < m + 010; i++) {
		map[i] = new int16[n + 010];
		for(int j = 0; j < n + 010; j++) {
			map[i][j] = 0;
		}
	}
	flag = new bool*[m + 010];
	for(int i = 0; i < m + 010; i++) {
		flag[i] = new bool[n + 010];
		for(int j = 0; j < n + 010; j++) {
			flag[i][j] = false;
		}
	}
	Map = map;
}

void search(int64 x, int64 y) {
	int64* ending = Ending;
	//flag[x][y] = true;
	if(x == ending[0] && y == ending[1]){
		sum++;
		return;
	}
	for(int i = 0; i <= 3; i++) {
		int64
		xNext = x + mx[i],
		yNext = y + my[i];
		if(xNext > m || yNext > n || xNext < 1 || yNext < 1)
			continue;
		if(flag[xNext][yNext])
			continue;
		if(Map[xNext][yNext] == 1)
			continue;
		flag[xNext][yNext] = true;
		search(xNext, yNext);
		flag[xNext][yNext] = false;
	}
	//flag[x][y] = false;
}

int index() {
	int64 beginning[2];
	int64* ending = Ending;
	int64 t;
	cin >> t;
	cin >> beginning[0] >> beginning[1];
	cin >> ending[0] >> ending[1];
	for(int64 i = 0; i < t; i++) {
		int64 temp[2];
		cin >> temp[0] >> temp[1];
		Map[temp[0]][temp[1]] = 1;
	}
	flag[beginning[0]][beginning[1]] = true;
	search(beginning[0], beginning[1]);
	cout << sum;
	return 0;
}
2021/5/22 16:24
加载中...