QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504947#9108. Zayin and Obstaclesikun#AC ✓139ms34620kbC++201.4kb2024-08-04 17:42:582024-08-04 17:42:58

Judging History

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

  • [2024-08-04 17:42:58]
  • 评测
  • 测评结果:AC
  • 用时:139ms
  • 内存:34620kb
  • [2024-08-04 17:42:58]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include <cstring>
#include<queue>
#include<array>
using namespace std;
#define endl '\n'
#define int long long
int n,m;
int mp[110][110][110];
int s[110][110][110];
int x1,y1,z1,x2,y2,z2;
int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int dis[110][110][110];

void bfs()
{
	queue<array<int,3>> q;
	q.push({x1,y1,z1});
	memset(dis,0x3f,sizeof dis);
	dis[x1][y1][z1]=0;
	while(q.size())
	{
		int x=q.front()[0];
		int y=q.front()[1];
		int z=q.front()[2];
		q.pop();
		for(int i=0;i<6;i++) {
			int dx=x+dir[i][0];
			int dy=y+dir[i][1];
			int dz=z+dir[i][2];
			if(dx>n||dy>n||dz>n||dx<1||dy<1||dz<1) continue;
			if(dis[dx][dy][dz]>dis[x][y][z]+1 && !mp[dx][dy][dz])
			{
				dis[dx][dy][dz]=dis[x][y][z]+1;
				q.push({dx,dy,dz});
			}
		}
	}
}


void solve() {
	cin>>n>>m;
	memset(s,0,sizeof s);
	for(int i=1;i<=m;i++) {
		int a,b,c,d,e,f;
		cin>>a>>b>>c>>d>>e>>f;
		for(int j=a;j<=d;j++) {
			for(int k=b;k<=e;k++){
				s[j][k][c]++;
				s[j][k][f+1]--;
			}
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			for(int k=1;k<=n;k++)
				mp[i][j][k]=mp[i][j][k-1]+s[i][j][k];
		}
	}
	//
	cin>>x1>>y1>>z1>>x2>>y2>>z2;
	bfs();
	if(dis[x2][y2][z2]>1e7)cout<<"-1\n";
	else cout<<dis[x2][y2][z2]<<endl;
}

signed main(){

	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--) solve();

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 25652kb

input:

3
3 0
1 1 1 3 3 3
3 1
2 1 1 2 3 3
1 1 1 3 3 3
3 3
2 1 1 2 2 3
1 1 2 2 3 2
1 2 2 3 3 2
1 1 1 1 1 3

output:

6
-1
14

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 21ms
memory: 33304kb

input:

5
19 27
2 1 1 2 18 19
4 2 1 4 19 19
6 1 1 6 18 19
8 2 1 8 19 19
10 1 1 10 18 19
12 2 1 12 19 19
14 1 1 14 18 19
16 2 1 16 19 19
18 1 1 18 18 19
1 1 2 18 19 2
2 1 4 19 19 4
1 1 6 18 19 6
2 1 8 19 19 8
1 1 10 18 19 10
2 1 12 19 19 12
1 1 14 18 19 14
2 1 16 19 19 16
1 1 18 18 19 18
1 2 2 19 19 2
1 2 4 ...

output:

1998
15998
53998
127998
249998

result:

ok 5 lines

Test #3:

score: 0
Accepted
time: 54ms
memory: 34212kb

input:

5
99 147
2 1 1 2 98 99
4 2 1 4 99 99
6 1 1 6 98 99
8 2 1 8 99 99
10 1 1 10 98 99
12 2 1 12 99 99
14 1 1 14 98 99
16 2 1 16 99 99
18 1 1 18 98 99
20 2 1 20 99 99
22 1 1 22 98 99
24 2 1 24 99 99
26 1 1 26 98 99
28 2 1 28 99 99
30 1 1 30 98 99
32 2 1 32 99 99
34 1 1 34 98 99
36 2 1 36 99 99
38 1 1 38 9...

output:

132878
2596
227782
37198
90672

result:

ok 5 lines

Test #4:

score: 0
Accepted
time: 135ms
memory: 34620kb

input:

5
99 1000
2 1 1 2 98 99
4 2 1 4 99 99
6 1 1 6 98 99
8 2 1 8 99 99
10 1 1 10 98 99
12 2 1 12 99 99
14 1 1 14 98 99
16 2 1 16 99 99
18 1 1 18 98 99
20 2 1 20 99 99
22 1 1 22 98 99
24 2 1 24 99 99
26 1 1 26 98 99
28 2 1 28 99 99
30 1 1 30 98 99
32 2 1 32 99 99
34 1 1 34 98 99
36 2 1 36 99 99
38 1 1 38 ...

output:

4998
4998
4998
4998
4998

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 27ms
memory: 33520kb

input:

5
19 1000
2 1 1 2 18 19
4 2 1 4 19 19
6 1 1 6 18 19
8 2 1 8 19 19
10 1 1 10 18 19
12 2 1 12 19 19
14 1 1 14 18 19
16 2 1 16 19 19
18 1 1 18 18 19
4 13 10 4 19 12
6 5 5 6 6 18
6 16 4 6 18 11
8 6 10 8 17 19
14 10 7 14 17 12
2 4 4 2 5 15
4 5 10 4 7 17
12 1 2 12 2 9
12 8 10 12 18 15
16 19 2 16 19 8
8 1 ...

output:

-1
798
1906
3198
4998

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 139ms
memory: 34144kb

input:

5
100 0
92 81 37 11 85 14
100 0
16 48 91 61 65 58
100 0
87 25 52 83 7 45
100 0
80 95 16 62 5 80
100 0
33 33 50 48 82 3

output:

108
95
29
172
111

result:

ok 5 lines