QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431830#5514. Mazehansiyuan#8 324ms590436kbC++141.5kb2024-06-06 09:59:522024-06-06 09:59:53

Judging History

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

  • [2024-06-06 09:59:53]
  • 评测
  • 测评结果:8
  • 用时:324ms
  • 内存:590436kb
  • [2024-06-06 09:59:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N=6e6+6;
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
int R,C,n;
int sx,sy,ex,ey;
string g[N];
struct nd{
	int stp,r,c;
	bool operator < (const nd &y) const{
		if(stp != y.stp) return stp<y.stp;
		return (r+c) < (y.r+y.c);
	}
};
vector<nd> dis[N];
vector<bool> vis[N];
struct nd2{
	int x,y;
	bool operator < (const nd2 &q) const{
		return dis[q.x][q.y] < dis[x][y];
	}
};
priority_queue<nd2> q;
int main(){
	scanf("%d%d%d",&R,&C,&n);
	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
	for(int i=1;i<=R;i++){
		dis[i].resize(C+1);
		vis[i].resize(C+1);
		cin>>g[i];
		g[i] = ' '+g[i];
		for(int j=1;j<=C;j++)
			dis[i][j] = nd{R+C+1,0,0};
	}
	dis[sx][sy] = nd{0,n,n};
	q.push(nd2{sx,sy});
	vis[sx][sy] = 1;
	while(q.size()){
		int x = q.top().x;
		int y = q.top().y;
		q.pop();
	//	printf("%d %d %d %d %d\n",x,y,dis[x][y].stp,dis[x][y].r,dis[x][y].c);
		if(x==ex && y==ey){
			printf("%d\n",dis[x][y].stp);
			return 0;
		}
		for(int i=0;i<4;i++){
			int xx = x+dx[i];
			int yy = y+dy[i];
			if(xx>R || yy>C || xx<1 || yy<1 || vis[xx][yy]) continue;
			nd t;
			if(dis[x][y].r==n && dis[x][y].c==n){
				if(g[xx][yy]=='.') t = dis[x][y];
				else t = nd{dis[x][y].stp+1,1,1};
			}
			else{
				t = dis[x][y];
				if(dx[i]) t.r++;
				if(dy[i]) t.c++;
				if(t.r>n || t.c>n) continue;
			}
			if(t < dis[xx][yy]){
				dis[xx][yy] = t;
				q.push(nd2{xx,yy});
				vis[xx][yy] = 1;
			}
		}
	}
	return 0;
}

詳細信息

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 82ms
memory: 566272kb

input:

31 32 1
25 22
5 3
################################
################################
.###############################
.###############################
##..###############.############
###.###############.############
#####.##########################
###.#.##########################
###.##############...

output:

26

result:

ok single line: '26'

Test #2:

score: 0
Accepted
time: 59ms
memory: 566508kb

input:

31 32 1
31 5
18 30
................................
..........................#.....
................................
.................#..............
................................
................................
....#...........................
................................
....................

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 63ms
memory: 566268kb

input:

31 32 1
7 10
1 32
.#...#.####...#.####..###..####.
.#.##.#..#.###.#.#####.#..#..##.
.#.#######.########..#.#....#.#.
####.##########.####.#..###...##
####.##....####.####..####.##.##
##.###..#####..#.###..#.##.#.#.#
####.###...##.........###.#.####
.##..##.##.######....##.#####.##
####.#.###.##.#......

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 75ms
memory: 566284kb

input:

31 32 1
18 18
1 18
#################.##############
################################
################################
################################
################################
################################
###############.################
################################
#################...

output:

15

result:

ok single line: '15'

Test #5:

score: 0
Accepted
time: 59ms
memory: 566272kb

input:

1 1000 1
1 597
1 432
..........................................................#..........................................................................................................................................#................................................................#...................

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 72ms
memory: 566260kb

input:

1 1000 1
1 354
1 826
#############################################################.#########################################################################################################################################################################################################################...

output:

463

result:

ok single line: '463'

Test #7:

score: 0
Accepted
time: 59ms
memory: 566256kb

input:

1 4 1
1 4
1 3
#...

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 68ms
memory: 566236kb

input:

1 45 1
1 8
1 20
#######.####.#####..#####################.###

output:

9

result:

ok single line: '9'

Test #9:

score: 0
Accepted
time: 51ms
memory: 566244kb

input:

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

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 55ms
memory: 566264kb

input:

1 2 1
1 1
1 2
..

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 89ms
memory: 566320kb

input:

1 148 1
1 91
1 89
.####.#.###...#..####..####.###..#...#.##.#####.######.#.#....#...####..##.#.#.##...##...#.##.#.#####.#####...#.#.###.#.#...##...###..#...##..##.###

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 55ms
memory: 566248kb

input:

2 84 1
1 11
1 62
.#..#.##.#.#.##.#.##.#.#...######.#.###...##.#####....##.##.#..###.###.##...##.#...#
.#....##.#.#..#...#....##..###..#.##.#...###.#.#.###...##.#....#...##.#..####.#.###.

output:

20

result:

ok single line: '20'

Test #13:

score: 0
Accepted
time: 76ms
memory: 566248kb

input:

1 59 1
1 6
1 20
#.###.########.###..##.####.###.##.##########.########..#.#

output:

11

result:

ok single line: '11'

Test #14:

score: 0
Accepted
time: 59ms
memory: 566268kb

input:

31 32 1
31 5
18 30
................................
..#...####.######..##.#.####.##.
..#.#.####.#####.##..######..#..
.##.####.#.#.#...##.##########..
..#...###.#####...####.#####.##.
.#..###....#.#.#.##..###.#..#.#.
.#.###..###.###.#####.#.#######.
..#...#.####.########...#..####.
..#..#.##...........

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 68ms
memory: 566264kb

input:

31 32 1
17 32
11 7
................................
.#.##.#..#.###.#######.#.###.##.
.#.#######.#########.#.#....#.#.
.###.##########.####.#..###.#.#.
.######.#..##########.####.##.#.
.#.###..######.#.###..#.##.#.#..
.###.###.#.##........######.###.
.##.###.##.######....##.#####.#.
.#####.###.####.....

output:

2

result:

ok single line: '2'

Test #16:

score: 0
Accepted
time: 64ms
memory: 566272kb

input:

31 32 1
7 11
13 25
................................
.##############################.
.##############################.
.##############################.
.##############################.
.##############################.
.#########.####.###############.
.##############################.
.################...

output:

11

result:

ok single line: '11'

Test #17:

score: 0
Accepted
time: 68ms
memory: 567300kb

input:

244 245 1
226 133
105 7
.####.##################################################.###.#############.########.#######.#########################################.################.####.#################.######################################.###########.######.#####.######.
.####.######.#####.#####.#####...

output:

163

result:

ok single line: '163'

Test #18:

score: 0
Accepted
time: 67ms
memory: 566480kb

input:

1 46212 1
1 39597
1 10273
#########################################.########################.##############################################################################################.##################.########.####################.##########################################.####################...

output:

28589

result:

ok single line: '28589'

Test #19:

score: 0
Accepted
time: 63ms
memory: 567160kb

input:

244 245 1
226 133
105 7
..................................................#...............................................................................................#........................................................#.........................................
.................................

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 75ms
memory: 567072kb

input:

244 245 1
214 117
83 245
.##..#.###.##.#.###.#..#####....#..##.##..##.##.#.###.#.##.####.###.....#.#...###.#.###..##.#.##.####..##..#..##....#.###.##.#########.#.#.##.##.#.####.##.##.##.#.##.##..##.##.#..#.#...##..##..#..#..#..####.#.###.##.#..#.#####....##.##.##.#.##..
#.###.##.#..###...###########...

output:

45

result:

ok single line: '45'

Test #21:

score: 0
Accepted
time: 81ms
memory: 567096kb

input:

244 245 1
15 226
207 34
########################################################################################################################################################################.############################################################################
##############################...

output:

340

result:

ok single line: '340'

Test #22:

score: 0
Accepted
time: 71ms
memory: 566924kb

input:

1 60000 1
1 59085
1 9263
.........................................................................................................................................................................................................................................................#............................

output:

496

result:

ok single line: '496'

Test #23:

score: 0
Accepted
time: 58ms
memory: 566624kb

input:

1 60000 1
1 57861
1 18234
##################.###########.##################.###################################################################.#################.#####.##########################################################################.###########################.#########.##################....

output:

39210

result:

ok single line: '39210'

Test #24:

score: 0
Accepted
time: 68ms
memory: 567076kb

input:

244 245 1
226 133
105 7
.....................................................................................................................................................................................................................................................
..#...#.#..####..####.......##...

output:

2

result:

ok single line: '2'

Test #25:

score: 0
Accepted
time: 55ms
memory: 567052kb

input:

244 245 1
214 117
83 245
.....................................................................................................................................................................................................................................................
..###.##.#..###...###########...

output:

8

result:

ok single line: '8'

Test #26:

score: 0
Accepted
time: 62ms
memory: 567060kb

input:

244 245 1
15 226
207 34
.....................................................................................................................................................................................................................................................
.#############################...

output:

44

result:

ok single line: '44'

Test #27:

score: 0
Accepted
time: 75ms
memory: 568160kb

input:

387 387 1
335 36
90 357
##########.##########.#######.#########.####.##########################.#################.##############################################################.######################.###################.##.###########.#####################.############.##################.#.#########...

output:

384

result:

ok single line: '384'

Test #28:

score: 0
Accepted
time: 70ms
memory: 566628kb

input:

2 30695 1
1 15156
1 6032
#..####.##..##..##.##.##..######.##.#.###.###########...####.#.###.#.###.#..###.#.###....###.#####..#...##.##.######.####.#######.######..#...#.#.##....##.##.#..#.#######.#.####.#.#####.##......###.#.#...#..#####.#.###.#####.############..###.#.#####.#...#.##...#..#.###..##....

output:

4487

result:

ok single line: '4487'

Test #29:

score: 0
Accepted
time: 84ms
memory: 568400kb

input:

387 387 1
55 282
267 35
.......................................................................................................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #30:

score: 0
Accepted
time: 96ms
memory: 568520kb

input:

387 387 1
287 270
56 102
#.#####.###..#..#.##..######...####..####.###..####.....#######.##..##..#.###.#..#..##.##.#...#.#.#.#.####.##...#.##..#.#.#..####.##.##.###......#.####..#####.####..##.#.#.#####..####.####.###.###..#.....#######.###.###.##..#.##..#...###..############.#.###.#..##.##..####.##...

output:

66

result:

ok single line: '66'

Test #31:

score: 0
Accepted
time: 101ms
memory: 568272kb

input:

387 387 1
182 105
119 379
##########################.######################################################################################################################################################################################################.################################################...

output:

312

result:

ok single line: '312'

Test #32:

score: 0
Accepted
time: 71ms
memory: 567872kb

input:

1 150000 1
1 113832
1 2038
.............................................................................#......................................................................................................................................................................................................

output:

1092

result:

ok single line: '1092'

Test #33:

score: 0
Accepted
time: 65ms
memory: 568088kb

input:

1 150000 1
1 6957
1 130571
####.##########################################################################.################################################################################.################################################.###############################################################...

output:

122389

result:

ok single line: '122389'

Test #34:

score: 0
Accepted
time: 83ms
memory: 568308kb

input:

387 387 1
55 282
267 35
.......................................................................................................................................................................................................................................................................................

output:

11

result:

ok single line: '11'

Test #35:

score: 0
Accepted
time: 82ms
memory: 568584kb

input:

387 387 1
287 270
56 102
......................................................................................................................................................................................................................................................................................

output:

35

result:

ok single line: '35'

Test #36:

score: 0
Accepted
time: 73ms
memory: 568176kb

input:

387 387 1
369 107
192 382
.....................................................................................................................................................................................................................................................................................

output:

21

result:

ok single line: '21'

Test #37:

score: 0
Accepted
time: 324ms
memory: 585656kb

input:

1224 1225 1
106 825
1167 186
##################################.#######.##..##.#.####.############.######.################.###################.#########.###########################.#####.####################.###############################.#######################.#######.########################.###...

output:

1112

result:

ok single line: '1112'

Test #38:

score: 0
Accepted
time: 69ms
memory: 568448kb

input:

16 10623 1
16 1171
14 2438
###.#....#.##..#.#.#.#.##.#.#..#.###..###.#..#...##..#.###..#...##.####.#......##...#..#..###...#..#####.#..##.#.###.#...#.##..#####.#######.....#.....#######.##.#....#.#...###..##..####.####.#.###.#####.#.##.###...#.....##.###.#.#.......#.###.##.#.###########.##.......##....

output:

185

result:

ok single line: '185'

Test #39:

score: 0
Accepted
time: 71ms
memory: 568496kb

input:

1 184339 1
1 58622
1 95339
.....#.....#.##.#.....#................#.....#.....#.#........#......................##.......#..#.....#....#.....##......#.................#............##.#....#..##......#...#.............#.......##.#............#.#....#....#...#...#..##.#...................#..#....##..#...

output:

5653

result:

ok single line: '5653'

Test #40:

score: 0
Accepted
time: 99ms
memory: 569028kb

input:

185 1158 1
170 697
18 48
#########.########.###.####.##########.################.#.##.#######.##.##.########.#.#############.####..###.##.####.###..###.####.#################.##..#######.#.###..#.#####..#.#.##.#.####.#.###########.####.###################..#####.############.###.#####.###..######..#...

output:

453

result:

ok single line: '453'

Test #41:

score: 0
Accepted
time: 71ms
memory: 569376kb

input:

2 121141 1
1 84070
2 47224
########.#.######.#.#####.##.###.##.####.#...####..#...#.#####.##.###.#.#######.##.##.######.###.#####.#####.####...#..#####.###########.####...#.########..##..####.###.###.####.###.#.###..####..###.##.####.##.#######.#..######.#.#....###.##.##.###.####...#.#.#.##.##.###.#...

output:

23385

result:

ok single line: '23385'

Test #42:

score: 0
Accepted
time: 112ms
memory: 575412kb

input:

6 123737 1
3 116020
4 86192
...#..#..#.............#.#.##.##...#..#...#...#...........#..#...#......##......#.#...#..#.##..#####..........#.#.....#.#.####......#....#.....##.##.####...........#.#.##..###.....#.#.#...#.#..#..#.#.#..#..#....#..#.......#...#...#...#.#.##..#..#..##......#..#...#...#.......

output:

1725

result:

ok single line: '1725'

Test #43:

score: 0
Accepted
time: 105ms
memory: 576152kb

input:

5 160357 1
1 41933
1 68874
##########.###.##.#.#####..#.#####.###..##.#############################.#############.##.#####.##########.##########.###.############..########.#####.#.######.###..####.####.##########.#####.###.##########..#.#######.##.###.#..#.###############.##############.###.###..###...

output:

20843

result:

ok single line: '20843'

Test #44:

score: 0
Accepted
time: 222ms
memory: 590436kb

input:

1224 1225 1
520 1165
390 755
.............................#....................................................................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #45:

score: 0
Accepted
time: 315ms
memory: 585740kb

input:

1224 1225 1
1155 1123
435 159
###....#.#.##.##.####.##.###.##########.##.####.#.#..##.##..#..####...#..#.....#####....####.###.#####...#..#..#....###.#....#....#.##.#.....##...##.#...##...####.####..#.#####.##..#.##.##.#.###.#..##.##.##..###.##..#.....#############.#####.#.##...##.#.####.#########.#...

output:

276

result:

ok single line: '276'

Test #46:

score: 0
Accepted
time: 257ms
memory: 585876kb

input:

1224 1225 1
533 1130
900 376
############################################################.###############################.########################.######################################################################.###############################################################.##################...

output:

1015

result:

ok single line: '1015'

Test #47:

score: 0
Accepted
time: 114ms
memory: 586464kb

input:

1 1500000 1
1 32769
1 947728
.................................................................................................................................................#................................................................................................................................

output:

9041

result:

ok single line: '9041'

Test #48:

score: 0
Accepted
time: 109ms
memory: 586552kb

input:

1 1500000 1
1 1314999
1 652665
##########################################################################################.###################################################.#############################################################################################.################################...

output:

655757

result:

ok single line: '655757'

Test #49:

score: 0
Accepted
time: 274ms
memory: 585812kb

input:

1224 1225 1
969 785
150 464
...................................................................................................................................................................................................................................................................................

output:

37

result:

ok single line: '37'

Test #50:

score: 0
Accepted
time: 219ms
memory: 585996kb

input:

1224 1225 1
1155 1123
435 159
.................................................................................................................................................................................................................................................................................

output:

49

result:

ok single line: '49'

Test #51:

score: 0
Accepted
time: 282ms
memory: 585712kb

input:

1224 1225 1
533 1130
900 376
..................................................................................................................................................................................................................................................................................

output:

407

result:

ok single line: '407'

Subtask #2:

score: 0
Wrong Answer

Test #52:

score: 19
Accepted
time: 95ms
memory: 566256kb

input:

3 6 2
2 1
3 3
...###
..##..
#..###

output:

0

result:

ok single line: '0'

Test #53:

score: 0
Accepted
time: 55ms
memory: 566256kb

input:

4 24 4
3 4
3 3
..#...##.#...###...###.#
.##.#..##.##.##..#.####.
#.......#.#.#...#.#####.
######....######.#...#.#

output:

0

result:

ok single line: '0'

Test #54:

score: -19
Wrong Answer
time: 74ms
memory: 566268kb

input:

2 136 2
1 133
2 45
#############################################.##################.#.#######.##############.#################.##############.##.######.###
####.########.###############.####.###..####.#.###.#################.##..##############.###.############################################

output:

42

result:

wrong answer 1st lines differ - expected: '41', found: '42'

Subtask #3:

score: 0
Wrong Answer

Test #64:

score: 16
Accepted
time: 77ms
memory: 566272kb

input:

35 60 20
3 60
2 44
.#....##.#.###..##.#.#....#.....#..#..#.##.#..#....###.####.
#.#......#.####..####...#...#......#........####....##.#.###
.#..#.....#.####..#.##..#.#.#...#.##..#.#..#######....#..##.
.#.#...##..#.##.......#......##......####...##.##..##.#....#
#...#.......#..#..#...#.#####.##.###....

output:

1

result:

ok single line: '1'

Test #65:

score: -16
Wrong Answer
time: 67ms
memory: 566744kb

input:

63 602 3
10 463
3 402
#.#.#..#..######.#.##.##.#########.###.##.##..#..####.#...#########..###..####.######.###.##.#.....############.####.########.#.########.##.######.###..#####.###..##.#..#..##..##.###..##.###.#######...#.##.##.#.#.##...##...####.###.##.#.#.....#####.##.#..#.##..#...######.#####....

output:

10

result:

wrong answer 1st lines differ - expected: '9', found: '10'

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #6:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%