dfs 为什么会mle
  • 板块P1605 迷宫
  • 楼主nrkz902
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/3/4 21:21
  • 上次更新2024/3/5 12:09:17
查看原帖
dfs 为什么会mle
677832
nrkz902楼主2024/3/4 21:21
#include <bits/stdc++.h>
using namespace std;
int n , m , t;
int sx , sy , fx , fy;

const int N = 12;
char g[N][N];
bool st[N][N];
int dx[] = {-1 , 0 , 1 , 0};
int dy[] = {0 , 1 , 0 , -1};

long long res = 0;

void dfs(int x , int y){
	if(x == fx && y == fy){
		res ++;
		return;
	}
	
	for(int i = 0 ; i < 4 ; i++){
		int a = x + dx[i];
		int b = y + dy[i];
		if(a>=1 && b >=1 && a<=n && b <= m && st[a][b]==0 && g[a][b]=='.'){
			st[a][b] == true;
			dfs(a  , b);
			st[a][b] == false;
		}
	}
	return;		
}


int main(){
	cin>>n>>m>>t;
	cin>>sx>>sy>>fx>>fy;
	for(int i = 1 ; i <= n ; i++){
		for(int j = 1 ; j <= m ; j++){
			g[i][j] = '.';
		}
	}
	while(t--){
		int a,  b;
		cin>>a>>b;
		g[a][b] = '#';
	}
	st[sx][sy] = true;
	dfs(sx , sy);
	cout<<res;
	return 0;
}

2024/3/4 21:21
加载中...