90分WA,第16,17个点错了,希望路过的巨佬指点一下
查看原帖
90分WA,第16,17个点错了,希望路过的巨佬指点一下
384064
kevin985楼主2021/7/31 09:51

码风很丑,请原谅

#include <bits/stdc++.h>
#define N 400
#define INF 0x7f7f7f7f
#define rint register int
#define el printf("\n")
#define add_q t.x = p.x + fx[i] , t.y = p.y + fy[i] , t.step = p.step + 1 , t.sy = p.sy , t.ys = p.ys
#define visit vis[t.x][t.y][t.sy][t.ys] = 1
using namespace std;
int n,m,c1,c2,d;
int sx,sy,tx,ty;
int a[N][N],b[N][N];
struct Node{
	int x,y,step,sy,ys;
}p,t,tt,ans,ma[N][N];
queue<Node>q;
bool vis[N][N][20][20],ene[N][N];
int fx[9] = {0,1,-1,0,0,1,1,-1,-1};
int fy[9] = {0,0,0,1,-1,-1,1,-1,1};
//a更优则返回1,否则返回0 
inline bool comp(Node a,Node b)
{
	if(a.step != b.step) return a.step < b.step;
	if(a.sy + a.ys != b.sy + b.ys) return a.sy + a.ys < b.sy + b.ys;
	return a.ys < b.ys;
}
//差分 
inline void around(int x,int y,int s)
{
	s--;
	for(int i=0;i<=s;i++)
	{
		b[max(1,x - i)][max(1,y - s + i)] ++;
		b[max(1,x - i)][min(m,y + s - i) + 1] --;
		b[min(n,x + i)][max(1,y - s + i)] ++;
		b[min(n,x + i)][min(m,y + s - i) + 1] --;
	}
}
//对差分数组求前缀和 
inline void total()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			b[i][j] += b[i][j - 1];
			if(b[i][j] > 0) a[i][j] = 1;
		}
	}
}
inline void debug_ans()
{
	printf("ans: x = %d y = %d step = %d sy = %d ys = %d\n",ans.x,ans.y,ans.step,ans.sy,ans.ys);
}
inline void debug_b()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<b[i][j]<<" ";
		}
		el;
	}
	el;
}
inline void debug_a()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<a[i][j]<<" ";
		}
		el;
	}
	el;
}
inline void debug()
{
	if(p.x == 1 && p.y == 5 || p.x == 4 && p.y == 5 || p.x == 7 && p.y == 5)  cout<<"___________________\n";
	printf("x = %d y = %d step = %d sy = %d ys = %d\n",p.x,p.y,p.step,p.sy,p.ys);
	if(p.x == 1 && p.y == 5 || p.x == 4 && p.y == 5 || p.x == 7 && p.y == 5)  cout<<"___________________\n";
}
inline bool onboard(int x,int y)
{
	if(x > 0 && x <= n && y > 0 && y <= m) return true;
	return false;
}
//超级大爆搜 
inline void bfs()
{
	ans.x = ans.y = 0,ans.step = ans.sy = ans.ys = INF;
//	if(q.empty()) cout<<"empty"<<endl;
//	else cout<<"Enter"<<endl;
	while(!q.empty())
	{
		p = q.front();
		q.pop();
		if(p.step > ma[p.x][p.y].step && p.sy > ma[p.x][p.y].sy && p.ys > ma[p.x][p.y].ys) continue;
		if(p.step <= ma[p.x][p.y].step && p.sy <= ma[p.x][p.y].sy && p.ys <= ma[p.x][p.y].ys)
		{
			ma[p.x][p.y].step = p.step;
			ma[p.x][p.y].sy = p.sy;
			ma[p.x][p.y].ys = p.ys;
		}
		if(comp(ans,p)) continue;
		if(p.ys > c1 || p.sy > c2)
		{
//			cout<<"Skill Limit"<<endl;
			continue;
		}
//		debug();
		if(p.x == tx && p.y == ty)
		{
//			cout<<"Arrive"<<endl;
//			cout<<comp(p,ans)<<endl;
			if(comp(p,ans))
			{
				ans.x = p.x;
				ans.y = p.y;
				ans.step = p.step;
				ans.sy = p.sy;
				ans.ys = p.ys;
//				debug_ans();
				continue;
			}
		}
		for(rint i=1;i<=8;++i)
		{
			add_q;
			if(!onboard(t.x,t.y) || ene[t.x][t.y]) continue;
			if(a[t.x][t.y] <= 0 && !vis[t.x][t.y][t.sy][t.ys])
			{
				visit;
				q.push(t);
			}
			t.ys = p.ys + 1;
			if(a[t.x][t.y] > 0 && !vis[t.x][t.y][t.sy][t.ys])
			{
				visit;
				q.push(t);
			}
		}
		for(rint i=1;i<=4;++i)
		{
			t.x = p.x + fx[i] * d;
			t.y = p.y + fy[i] * d;
			t.step = p.step + 1;
			t.sy = p.sy + 1;
			t.ys = p.ys;
			if(!onboard(t.x,t.y) || ene[t.x][t.y]) continue;
			if(!vis[t.x][t.y][t.sy][t.ys] && a[t.x][t.y] <= 0 && !ene[t.x][t.y])
			{
				visit;
				q.push(t);
			}
			t.ys = p.ys + 1;
			if(!vis[t.x][t.y][t.sy][t.ys] && a[t.x][t.y] > 0 && !ene[t.x][t.y])
			{
//				cout<<"x = "<<t.x<<" y = "<<t.y<<" is invisable"<<endl;
				visit;
				q.push(t);
			}
		}
	}
}
int main()
{
//	freopen("bandit18.in","r",stdin);
	freopen("P6474_16.in","r",stdin);
	scanf("%d%d%d%d%d",&n,&m,&c1,&c2,&d);
	for(rint i=1;i<=n;++i)
	{
		for(rint j=1;j<=m;++j)
		{
			ma[i][j].step = ma[i][j].sy = ma[i][j].ys = INF;
			string s;
			cin>>s;
			if(s[0] == '.')
			{
				a[i][j] = 0;
			}else if(s[0] == 'S')
			{
				t.x = sx = i;
				t.y = sy = j;
				t.sy = t.ys = 0;
				vis[i][j][0][0] = 1;
				q.push(t);
			}else if(s[0] == 'T')
			{
				tx = i;
				ty = j;
			}else{
				int x = 0;
				for(rint k=s.size() - 1;k>=0;--k)
				{
					x = x * 10 + (s[k] - '0');
				}
				a[i][j] = 1; ene[i][j] = 1;
				around(i , j , x);
			}
		}
	}
	total();
//	el;
	bfs();
	if(ans.step == INF) printf("-1");
	else printf("%d %d %d",ans.step,ans.ys,ans.sy);
	return 0;
}
2021/7/31 09:51
加载中...