QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100574#411. Dangerous Skatinglmeowdn0 0ms0kbC++141.9kb2023-04-26 20:15:562023-04-26 20:15:58

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-26 20:15:58]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
  • [2023-04-26 20:15:56]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
	int x=0,w=1; char c=getchar(); 
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
	return x*w;
}

const int N=1009,inf=0x3f3f3f3f; 

int n,m,sx,sy,tx,ty,vst[N*N],id[N][N],tot,p[N][N][4],d[N*N];
char s[N][N];
vp e[N*N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int dijkstra(int s,int t) {
	priority_queue<pii>q; q.push(pii(0,s));
	memset(d,0x3f,sizeof(d)); d[s]=0;
	while(!q.empty()) {
		int u=q.top().se; q.pop();
		if(vst[u]) continue; vst[u]=1;
		for(auto [v,w]:e[u]) if(d[v]>d[u]+w)
			d[v]=d[u]+w, q.push(pii(-d[v],v));
	} return d[t];
}

signed main() {
	freopen("tmp.in","r",stdin);
	n=read(), m=read();
	rep(i,1,n) scanf("%s",s[i]+1);
	sx=read(), sy=read(), tx=read(), ty=read();
	rep(i,1,n) rep(j,1,m) if(s[i][j]=='.') id[i][j]=++tot;
	rep(i,1,n) rep(j,1,m) if(id[i][j]) {
		rep(k,0,3) if(id[i+dx[k]][j+dy[k]])
			e[id[i][j]].eb(id[i+dx[k]][j+dy[k]],2);
	}
	per(i,n,1) per(j,m,1) if(id[i][j]) {
		rep(k,0,1) {
			if(!id[i+dx[k]][j+dy[k]]) p[i][j][k]=id[i][j];
			else p[i][j][k]=p[i+dx[k]][j+dy[k]][k];
			e[id[i][j]].eb(p[i][j][k],1);
		}
	}
	rep(i,1,n) rep(j,1,m) if(id[i][j]) {
		rep(k,2,3) {
			if(!id[i+dx[k]][j+dy[k]]) p[i][j][k]=id[i][j];
			else p[i][j][k]=p[i+dx[k]][j+dy[k]][k];
			e[id[i][j]].eb(p[i][j][k],1);
		}
	}
	if(!id[sx][sy]||!id[tx][ty]) return puts("-1"), 0;
	int res=dijkstra(id[sx][sy],id[tx][ty]);
	if(res==inf) puts("-1"); else printf("%d\n",res);
	return 0;
}

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

10 10
##########
#....#.###
#.......##
#........#
#.......##
##.......#
#.......##
#.....#.##
#.....#..#
##########
4 7
8 5

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

input:

200 200
########################################################################################################################################################################################################
#.............................................................................................

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #27:

score: 0
Time Limit Exceeded

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:


result: