DFS TLE不知道怎么优化
  • 板块P1141 01迷宫
  • 楼主Stevehim
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/8/24 16:13
  • 上次更新2023/10/27 13:52:02
查看原帖
DFS TLE不知道怎么优化
759274
Stevehim楼主2022/8/24 16:13

蒟蒻还不怎么会bfs只能dfs。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int start_x, start_y;
char a[1005][1005];
//char aa[1005][1005]; //用于保存原始地图,用于重置
int flag[1005][1005]; //标记来过 
int m;
int n;
long long int sum = 0;
void dfs(int x, int y,int num){
	flag[y][x] = -1; //标记,不会再走这里 
	if(a[y][x+1]-'0' == !num && flag[y][x+1] == 1){
		dfs(x+1,y,!num); 
	}
	if(a[y][x-1]-'0' == !num && flag[y][x-1] == 1){
		dfs(x-1,y,!num); 
	}
	if(a[y+1][x]-'0' == !num && flag[y+1][x] == 1){
		dfs(x,y+1,!num); 
	}
	if(a[y-1][x]-'0' == !num && flag[y-1][x] == 1){
		dfs(x,y-1,!num); 
	}
	return;
}

void _reload(){
	for(int i =0; i<= n; i++){
		for(int j = 0; j <= n; j++){
			flag[i][j] = 1;
		}
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	_reload();
	for(int i = 0; i < n; i++){
		scanf("%s",&a[i]);
	}
	for(int i = 0; i < m; i++){
		scanf("%d %d",&start_y,&start_x);
		start_y--;
		start_x --;
		dfs(start_x,start_y,a[start_y][start_x]-'0');
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(flag[i][j] == -1){
					sum++;
				}
			} 
		}
		printf("%lld\n",sum);
		_reload();
		sum = 0;
	}
    return 0;
}

求解答 谢谢!

2022/8/24 16:13
加载中...