蒟蒻TLE80分求助
查看原帖
蒟蒻TLE80分求助
98490
houzhiyuan楼主2020/5/12 17:03
#include<bits/stdc++.h>
using namespace std;
int n,m,c1,c2,d,b[351][351],sx1,sy1,sx2,sy2;
struct hzy{
	int x,y,c1,c2,z;
};
struct hzy1{
	int z,c1,c2;
}bb[351][351]; 
queue<hzy> q;
string ch;
int qq[8]= {0,1,0,-1,1,-1,1,-1};
int w[8]= {1,0,-1,0,1,-1,-1,1};
bool map1[351][351];
bool qs(int x,int y,int z,int c1,int c2){
	if(z<bb[x][y].z){
		return true;
	}
	else{
		if(z==bb[x][y].z){
			if(c1+c2>bb[x][y].c1+bb[x][y].c2){
				return true;
			}
			else{
				if(c1+c2==bb[x][y].c1+bb[x][y].c2){
					if(c1>bb[x][y].c1){
						return true;
					}
				}
			}
		}
	}
	return false;
}
int main() {
	cin>>n>>m>>c1>>c2>>d;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>ch;
			if(ch=="S") {
				sx1=i;
				sy1=j;
			}
			if(ch=="T") {
				sx2=i;
				sy2=j;
			}
			if(ch!="T"&&ch!="S"&&ch!=".") {
				map1[i][j]=1;
				int xx=0;
				for(int i=0; i<ch.size(); i++)
					xx=(xx<<1)+(xx<<3)+(ch[i]^'0');
				for(int k=max(i-xx+1,0); k<=min(i+xx-1,n); k++) {
					int yy=xx-1-abs(k-i);
					b[k][max(j-yy,0)]++;
					b[k][min(j+yy,m)+1]--;
				}
			}
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			b[i][j]+=b[i][j-1];
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			if(map1[i][j]) {
				b[i][j]=-1;
			} else {
				if(b[i][j])b[i][j]=1;
			}
		}
	}
	memset(bb,10,sizeof(bb));
	q.push((hzy) {sx1,sy1,c1,c2,0});
	bb[sx1][sy1].z=0;
	bb[sx1][sy1].c1=c1;
	bb[sx1][sy1].c2=c2;
	while(q.size()) {
		hzy xx=q.front();
		q.pop();
		if(xx.x==sx2&&xx.y==sy2){
			cout<<xx.z<<' '<<c1-xx.c1<<' '<<c2-xx.c2<<endl;
			return 0;
		}
		for(int i=0; i<8; i++) {
			int x=xx.x+qq[i];
			int y=xx.y+w[i];
			if(x>=1&&x<=n&&y>=1&&y<=m&&b[x][y]==0&&qs(x,y,xx.z+1,c1,c2)) {
				q.push((hzy) {x,y,xx.c1,xx.c2,xx.z+1});
				bb[x][y].z=xx.z+1;
				bb[x][y].c1=c1;
				bb[x][y].c2=c2;
			}
			x=xx.x+qq[i]*d;
			y=xx.y+w[i]*d;
			if(i<4&&xx.c2&&x>=1&&x<=n&&y>=1&&y<=m&&b[x][y]==0&&qs(x,y,xx.z+1,c1,c2+1)) {
				q.push((hzy) {x,y,xx.c1,xx.c2-1,xx.z+1});
				bb[x][y].z=xx.z+1;
				bb[x][y].c1=c1-1;
				bb[x][y].c2=c2;
			}
			if(xx.c1) {
				x=xx.x+qq[i];
				y=xx.y+w[i];
				if(x>=1&&x<=n&&y>=1&&y<=m&&b[x][y]==1&&qs(x,y,xx.z+1,c1+1,c2)) {
					q.push((hzy) {x,y,xx.c1-1,xx.c2,xx.z+1});
					bb[x][y].z=xx.z+1;
					bb[x][y].c1=c1;
					bb[x][y].c2=c2-1;
				}
				x=xx.x+qq[i]*d;
				y=xx.y+w[i]*d;
				if(i<4&&xx.c2&&x>=1&&x<=n&&y>=1&&y<=m&&b[x][y]==1&&qs(x,y,xx.z+1,c1+1,c2+1)) {
					q.push((hzy) {x,y,xx.c1-1,xx.c2-1,xx.z+1});
					bb[x][y].z=xx.z+1;
					bb[x][y].c1=c1-1;
					bb[x][y].c2=c2-1;
				}
			}
		}
	}
	cout<<-1;
	return 0;
}
2020/5/12 17:03
加载中...