QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#230743#6739. Teleportdingdingtang11514WA 83ms602460kbC++141.8kb2023-10-28 20:39:072023-10-28 20:39:08

Judging History

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

  • [2023-10-28 20:39:08]
  • 评测
  • 测评结果:WA
  • 用时:83ms
  • 内存:602460kb
  • [2023-10-28 20:39:07]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
namespace Mine{
	inline int read(){
		int x=1,a=0;
		char ch=getchar();
		while(ch>'9' || ch<'0')x=(ch=='-')?-1:x,ch=getchar();
		while(ch>='0' && ch<='9')
			a=(a<<1)+(a<<3)+(ch-'0'),ch=getchar();
		return a*x;
	}
	const int N=5005;
	int n,k;
	char ch[N][N];
	int fa[N*N],dep[N*N];
	inline int get(int x,int y){
		return (x-1)*N+y;
	}
	void init(){
		for(int i=0;i<N*N;i++)
			fa[i]=i,dep[i]=1;
		return ;
	}
	int find(int x){
		return (fa[x]==x) ?  x: fa[x]=find(fa[x]);
	}
	void merge(int x,int y){
		x=find(x),y=find(y);
		fa[x]=y;
	}
	int dist[N*N];
	queue<int> q;
	int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
	void gmin(int &x,int y){if(y<x)x=y; return ;}
	bool book[N*N];
	int bfs(){
		q.push(get(1,1));
		memset(dist,0x3f,sizeof dist);
		dist[get(1,1)]=0;
		while(q.size()){
			int tmp=q.front(),u;
			u=tmp;
			q.pop();
			if(book[u]) continue;
			book[u]=1;
			int nx,ny;
			int y=u%N,x=u/N+1;
			// cout<<x<<" "<<y<<endl;
			// if(ch[x][y]=='*') continue;
			for(int i=0;i<4;i++){
				nx=x+dx[i],ny=y+dy[i];
				// cout<<nx<<" "<<ny<<endl;
				if(nx<1 || nx>n || ny<1 || ny>n) continue;
				if(ch[nx][ny]=='*') continue;
				gmin(dist[get(nx,ny)],dist[u]+1);
				q.push(get(nx,ny));
			}
			u=find(u);
			ny=u%N,nx=u/N+1;
			while((ny+nx)-(x+y)<k){
				merge(get(nx,ny),get(ny+1,nx));
				swap(nx,ny);
				nx++;
				if(ch[nx][ny]!='*')
				gmin(dist[get(nx,ny)],dist[get(x,y)]+1);
			}
		}
		return dist[get(n,n)];
	}
	signed main(){
		init();
		n=read(),k=read();
		for(int i=1;i<=n;i++){
			scanf("%s",ch[i]+1);
		}
		printf("%lld",bfs());
		return 0;
	}
}
signed main(){
	 // freopen("play.in","r",stdin);
	 // freopen("play.out","w",stdout);
	return Mine::main();
}

詳細信息

Test #1:

score: 100
Accepted
time: 51ms
memory: 593860kb

input:

3 2
.*.
.*.
...

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 43ms
memory: 593668kb

input:

3 3
.*.
.*.
...

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: -100
Wrong Answer
time: 83ms
memory: 602460kb

input:

961 4
...*.*..*.....*.*..*..*..*.*.*.*.....*.....*....*..*...*....*.........*....*....*...*......*..*..*...*..*...*.....*...*...*.*.*.........**..**.......*.......*...*...*.*.*........*....*..*..*...*.....*.*......**.**..**...*..*.**.....*....*.*.*..*..*..*.*..*.*..*......*..*..*.*......*...*.*...*....

output:

2511

result:

wrong answer 1st numbers differ - expected: '540', found: '2511'