这个超时怎么优化呀?
查看原帖
这个超时怎么优化呀?
183603
SUNCHAOYI楼主2020/5/1 18:51

求各位dalao\texttt{dalao}帮助!!!

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 360;
int n,m,c1,c2,d,sx,sy,fx,fy,anst = INF,ansu1 = INF,ansu2 = INF;
int dx[8] = {0,0,1,-1,1,-1,1,-1},dy[8] = {1,-1,0,0,1,-1,-1,1};
int dis[MAX][MAX],tag[MAX][MAX];string str;
bool vis[MAX][MAX],area[MAX][MAX],walk[MAX][MAX],ok = 0;
void search(int x,int y,int u1,int u2,int time);
void work(int x,int y,int num);
int main()
{
	memset(dis,INF,sizeof(dis));
	//freopen("bandit.in","r",stdin);
	//freopen("bandit.out","w",stdout);
	cin>>n>>m>>c1>>c2>>d; 
	for(register int i = 1;i <= n;++i)
	{
		for(register int j = 1;j <= m;++j)
		{
			cin>>str;
			if(str == "S") sx = i,sy = j;
			else if(str == "T") fx = i,fy = j;
			else if(str == ".") ;
			else
			{
				vis[i][j] = 1;int number = 0;
				for(register int i = 0;i < str.size();++i) number = number * 10 + str[i] - '0';
				work(i,j,number - 1); 
			}
		}
	}
	for(register int i = 1;i <= n;++i)
	{
        int sum = 0;
        for(register int j = 1;j <= m;++j)
		{
            sum += tag[i][j];
            if(sum > 0) area[i][j] = 1;  
        }
    }   
	dis[sx][sy] = 0;
	search(sx,sy,0,0,0);
	if(!ok) cout<<-1<<endl;
	else cout<<anst<<" "<<ansu1<<" "<<ansu2<<endl;
	return 0;
}
void work(int x,int y,int num)
{
	for(register int i = 0;i <= num;++i)//差分 
	{
        ++tag[max(x - i,1)][max(y - (num - i),1)]; 
        --tag[max(x - i,1)][min(y + (num - i),m) + 1];
        ++tag[min(x + i,n)][max(y - (num - i),1)];
        --tag[min(x + i,n)][min(y + (num - i),m) + 1];
    }
}
void search(int x,int y,int u1,int u2,int time)
{
	if(dis[x][y] < time) return;
	dis[x][y] = time;
	if(x == fx && y == fy)
	{
		if(anst > time) anst = time,ansu1 = u1,ansu2 = u2;
		if(anst == time) 
		{
			if(u1 + u2 < ansu1 + ansu2) ansu1 = u1,ansu2 = u2;
			if(u1 + u2 == ansu1 + ansu2)
				if(u1 < ansu1) ansu1 = u1,ansu2 = u2;
		} 
		ok = 1;
		return;
	}
	for(register int i = 0;i < 8;++i)
	{
		int xx = x + dx[i],yy = y + dy[i];
		if(!vis[xx][yy] && 1 <= xx && 1 <= yy && xx <= n && yy <= m)
		{
			if(area[xx][yy] && u1 < c1) search(xx,yy,u1 + 1,u2,time + 1);
			if(!area[xx][yy]) search(xx,yy,u1,u2,time + 1);
		}
	}
	for(register int i = 0;i < 4;++i)
	{
		int xx = x + dx[i] * d,yy = y + dy[i] * d;
		if(!vis[xx][yy] && 1 <= xx && 1 <= yy && xx <= n && yy <= m)
		{
			if(area[xx][yy] && u1 < c1 && u2 < c2) search(xx,yy,u1 + 1,u2 + 1,time + 1);
			if(!area[xx][yy] && u2 < c2) search(xx,yy,u1,u2 + 1,time + 1);
		}
	}
}
2020/5/1 18:51
加载中...