QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#688071#8236. Snake MoveshinonomezhouRE 1ms3596kbC++231.8kb2024-10-29 23:07:462024-10-29 23:07:47

Judging History

你现在查看的是最新测评结果

  • [2024-10-29 23:07:47]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3596kb
  • [2024-10-29 23:07:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+10;
const ll INF=1e18;
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define fi first
#define se second
ll n,m,k;
//ll f[N][N],flag[N][N];
//bool re[N][N];
vector<vector<char> >maze(n+10,vector<char>(m+10));
vector<vector<ll> >f(n+10,vector<ll>(m+10,INF));
vector<vector<ll> >flag(n+10,vector<ll>(m+10));
vector<vector<bool> >re(n+10,vector<bool>(m+10));
//char maze[N][N];
priority_queue<plll,vector<plll>,greater<plll> >q;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
bool dead(ll x,ll y){
	if(x<1||x>n||y<1||y>m||maze[x][y]=='#')return true;
	else return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>m>>k;
	
//	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j]=INF;
	for(int i=1;i<=k;i++){
//		cout<<"y\n";
		ll x,y;
		cin>>x>>y;
		flag[x][y]=k-i;
		if(i==1)q.push({0,{x,y}}),f[x][y]=0;
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>maze[i][j];
		}
	}
	
	while(q.size()){
		plll p=q.top();
		q.pop();
		ll dis=p.fi;
		ll tx=p.se.fi,ty=p.se.se;
		if(re[tx][ty])continue;
		re[tx][ty]=true;
		for(int i=0;i<4;i++){
			ll nx=tx+dx[i],ny=ty+dy[i];
			if(dead(nx,ny))continue;
			if(re[nx][ny])continue;
			if(f[nx][ny]>max(dis+1,flag[nx][ny]+1)){
				f[nx][ny]=max(dis+1,flag[nx][ny]+1);
				q.push({f[nx][ny],{nx,ny}});
			}
			
			
			
		}
		
	}
	ll ans=0;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			if(flag[i][j]!=0)cout<<k-flag[i][j]<<' ';
//			else cout<<maze[i][j]<<' ';
//		}
//		cout<<'\n';
//	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(f[i][j]==INF)continue;
			ans+=f[i][j]*f[i][j];
//			cout<<f[i][j]<<' ';
		}
//		cout<<'\n';
	}
	cout<<ans;
	
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3556kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Runtime Error

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:


result: