用vector没用queue爆MLE求改
查看原帖
用vector没用queue爆MLE求改
1103295
butterbutterfly楼主2024/8/22 21:57
#include <iostream>
#include<cstring>
#include <cmath>
#include <vector>
#include <utility>
short n,m;
short start_x,start_y;
short ** map;
short max_step;

short incre_x[8]={-2,-1,1,2,2,1,-1,-2};
short incre_y[8]={-1,-2,-2,-1,1,2,2,1};

void draw(void)
{
	for(short i=0;i<n;i++)
	{
		for(short j=0;j<m;j++)
			std::cout<<map[i][j]<<' ';
		std::cout<<std::endl; 
	}
	std::cout<<std::endl; 
}

void bfs(short **ma,short step,std::vector<std::pair<short,short> >& arr)
{
	if(step>max_step)
		return ;
	int num=arr.size();
	std::vector<std::pair<short,short> > arr_next;
	//std::cout<<num<<std::endl;
	for(int i=0;i<num;i++)
	{
		ma[arr[i].first][arr[i].second]=step;
		for(short j=0;j<8;j++)
		{
			if(arr[i].first+incre_x[j]>=0&&arr[i].first+incre_x[j]<n&&arr[i].second+incre_y[j]>=0&&arr[i].second+incre_y[j]<m&&ma[arr[i].first+incre_x[j]][arr[i].second+incre_y[j]]==-1)
			{
				arr_next.push_back(std::make_pair(arr[i].first+incre_x[j],arr[i].second+incre_y[j]));
			}
		}
	}
	//draw();
	arr.clear();
	bfs(ma,step+1,arr_next);
}

int main (void)
{
	std::cin>>n>>m>>start_x>>start_y;
	
	map=new short * [n];
	
	for(short i=0;i<n;i++)
	{
		map[i]=new short[m]();
		memset(map[i],-1,sizeof(short)*m);
	}
	
	
	max_step=std::max(n,m);
	std::vector<std::pair<short,short> > arr;
	arr.push_back(std::make_pair(start_x-1,start_y-1));
	bfs(map,0,arr);
	//std::cout<<max_step<<std::endl;
	for(short i=0;i<n;i++)
	{
		for(short j=0;j<m;j++)
			std::cout<<map[i][j]<<' ';
		std::cout<<std::endl; 
	}
		
	return 0;
 } 
2024/8/22 21:57
加载中...