ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211425 | #3803. 激光 | mygr | 45 | 18943ms | 108676kb | C++ | 2.9kb | 2024-08-11 11:54:15 | 2024-08-11 13:14:06 |
answer
#include<bits/stdc++.h>
using namespace std;
const int Max=1005;
int tx[8]={0,-1,1,0,0},ty[8]={0,0,0,-1,1};
int Map[Max][Max][5],to[Max][Max][2];
bool vis[Max][Max];
char c[Max][Max];
int n,m;
char getc()
{
char c=getchar();
while(c!='.' and c!='#' and c!='/' and c!='\\' and c!='X')
c=getchar();
return c;
}
int dfs(int x,int y,int tow)
{
int ans=0;
if(Map[x][y][tow])
return ans;
if(!vis[x][y])
ans++;
vis[x][y]=1;
Map[x][y][tow]=1;
if(c[x][y]=='\\')
tow=(tow+1)%4+1;
else if(c[x][y]=='/')
{
if(tow==1)tow=4;
else if(tow==4)tow=1;
else if(tow==2)tow=3;
else if(tow==3)tow=2;
}
int nx=x+tx[tow],ny=y+ty[tow];
if(nx<1 or nx>n or ny<1 or ny>m or c[nx][ny]=='#')
return ans;
if(c[nx][ny]=='X')
{
if(!vis[nx][ny])
{
vis[nx][ny]=1;
ans++;
}
x=nx;y=ny;
nx=to[x][y][0];
ny=to[x][y][1];
}
ans+=dfs(nx,ny,tow);
return ans;
}
int dfn[Max][Max],cnt,low[Max][Max];
void clear()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
low[i][j]=dfn[i][j]=vis[i][j]=0;
for(int k=1;k<=4;k++)
Map[i][j][k]=0;
}
}
cnt=0;
}
void solve1()
{
for(int k=1;k<=4;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(c[i][j]=='.')
{
clear();
printf("%d ",dfs(i,j,k));
}
else
printf("-1 ");
}
printf("\n");
}
}
}
int dfs2(int x,int y,int tow)
{
int ans=1;
low[x][y]=dfn[x][y]=++cnt;
if(Map[x][y][tow])
return Map[x][y][tow];
int nx=x+tx[tow],ny=y+ty[tow];
if(nx<1 or nx>n or ny<1 or ny>m or c[nx][ny]=='#')
return Map[x][y][tow]=ans;
vis[x][y]=1;
if(c[nx][ny]=='X')
{
if(!vis[nx][ny])
{
vis[nx][ny]=1;
ans++;
}
int yx=nx,yy=ny;
nx=to[yx][yy][0];
ny=to[yx][yy][1];
cnt++;
}
if(!dfn[nx][ny])
{
dfs2(nx,ny,tow);
low[x][y]=min(low[x][y],low[nx][ny]);
if(low[nx][ny]<=dfn[x][y])
Map[x][y][tow]=Map[nx][ny][tow];
else
Map[x][y][tow]=Map[nx][ny][tow]+ans;
}
else
{
low[x][y]=min(low[x][y],dfn[nx][ny]);
if(vis[nx][ny])
{
Map[x][y][tow]=dfn[x][y]-low[x][y]+ans;
}
else
{
Map[x][y][tow]=Map[nx][ny][tow]+ans;
}
}
vis[x][y]=0;
return Map[x][y][tow];
}
void solve2()
{
for(int k=1;k<=4;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(c[i][j]=='.')
{
if(!Map[i][j][k])
dfs2(i,j,k);
printf("%d ",Map[i][j][k]);
}
else
printf("-1 ");
}
printf("\n");
}
clear();
}
}
int main()
{
scanf("%d%d",&n,&m);
int k=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
c[i][j]=getc();
if(c[i][j]=='X')
k++;
}
}
int X1,X2,Y1,Y2;
for(int i=1;i<=k/2;i++)
{
scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
to[X1][Y1][0]=X2;
to[X1][Y1][1]=Y2;
to[X2][Y2][0]=X1;
to[X2][Y2][1]=Y1;
}
if(n<=60 and m<=60)
solve1();
else
solve2();
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 3
Accepted
time: 121ms
memory: 1944kb
input:
50 50 .......................#.........#................ ..............................................
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 10000 tokens
Test #2:
score: 3
Accepted
time: 110ms
memory: 13028kb
input:
500 500 ...............................................................................................
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 1000000 tokens
Test #3:
score: 3
Accepted
time: 393ms
memory: 30664kb
input:
1000 1000 #.....#..#...............#..#.##......#......#...........#....#....#.#.......#..........##...
output:
-1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 1 -1...
result:
ok 4000000 tokens
Test #4:
score: 3
Accepted
time: 426ms
memory: 30436kb
input:
990 831 ...............................................................................................
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 3290760 tokens
Test #5:
score: 3
Accepted
time: 650ms
memory: 30736kb
input:
1000 1000 .............................................................................................
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 4000000 tokens
Test #6:
score: 3
Accepted
time: 0ms
memory: 1264kb
input:
3 3 /X\ X.X .X/ 1 2 2 3 2 1 3 2
output:
-1 -1 -1 -1 7 -1 7 -1 -1 -1 -1 -1 -1 4 -1 1 -1 -1 -1 -1 -1 -1 4 -1 1 -1 -1 -1 -1 -1 -1 7 -...
result:
ok 36 tokens
Test #7:
score: 3
Accepted
time: 0ms
memory: 1328kb
input:
7 7 /X.X.X\ X\.\./X ....... X\././X ....... X\./.\X \X.X.X/ 1 2 7 2 1 4 7 4 1 6 7 6 2 1 2 7 4 1 4 7 ...
output:
-1 -1 1 -1 1 -1 -1 -1 -1 2 -1 2 -1 -1 18 27 3 27 3 27 18 -1 -1 4 -1 4 -1 -1 18 27 5 27 5 27 18 ...
result:
ok 196 tokens
Test #8:
score: 3
Accepted
time: 0ms
memory: 1356kb
input:
9 10 #./....\.. ..../.X..# /.X..../.. ./.\./.... ..X../..#. \/.\...\.. ..X...\/.. .X....X..\ ....X.....
output:
-1 1 -1 1 1 1 1 -1 1 1 1 2 17 2 -1 2 -1 12 2 -1 -1 3 -1 3 11 3 28 -1 3 1 28 -1 22 -1 12 -1 28 4 4...
result:
ok 360 tokens
Test #9:
score: 3
Accepted
time: 47ms
memory: 2076kb
input:
50 50 .././.\.\\.\\.\/\\.//..\\..//\./////..\//..//\\... \.....\..../\\/..\/././\.//.\\\.\\/\\\..\//...
output:
1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 1 -...
result:
ok 10000 tokens
Test #10:
score: 3
Accepted
time: 162ms
memory: 2380kb
input:
60 60 X..XXX.../...XXX././X..\..X....XX.X.X./X....XXX....\XXX.X.X. XX..XX.//..XX\.X...X.X...X.....X....
output:
-1 1 1 -1 -1 -1 1 1 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1 1 1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 1...
result:
ok 14400 tokens
Test #11:
score: 3
Accepted
time: 108ms
memory: 2380kb
input:
60 60 X..XXXX..X...XXX.X.XX..X..XXXXXXX.X.X.XXX.X.XXXX.X.XXXX.XXX. XX..XX.XX..XXX.X...X.X.XXX..X..X....
output:
-1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1...
result:
ok 14400 tokens
Test #12:
score: 3
Accepted
time: 324ms
memory: 2108kb
input:
60 60 /..........................................................\ ./..................................
output:
-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
ok 14400 tokens
Test #13:
score: 3
Accepted
time: 574ms
memory: 2364kb
input:
60 55 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX. X\.........XX....X.X...XX../\../...X.....
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 13200 tokens
Test #14:
score: 3
Accepted
time: 580ms
memory: 2384kb
input:
60 60 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX. X...\\XXX//../X/////...\..\.\/X.X...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 14400 tokens
Test #15:
score: 3
Accepted
time: 479ms
memory: 2384kb
input:
60 60 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX. X/..\\/..//.././////...\..\.\/......
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 14400 tokens
Test #16:
score: 0
Wrong Answer
time: 598ms
memory: 38764kb
input:
1000 899 ........X...X..X...X.X.....X.....X...............X.XX.X.X............X..X.X.X..X..............
output:
1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 1 -1 1 1 1 -1 1 -1 1 1 1 1 1 -1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
wrong answer 912th words differ - expected: '302', found: '2'
Test #17:
score: 0
Wrong Answer
time: 944ms
memory: 38764kb
input:
1000 1000 X.....XXXX.X...X.........X..X.XX...X.XX......X........X..X....X....X.X.......X.......X..XX...
output:
-1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 -1 1 1 1 -1 1 -1 -1 1 1 1 1 ...
result:
wrong answer 1008th words differ - expected: '165', found: '2'
Test #18:
score: 0
Wrong Answer
time: 1197ms
memory: 38936kb
input:
1000 1000 XXX...XXXXXXXXXXXXXX.XXXXXXXXXXXXXXX.XXX.X.XXXXXX.XX..X.XXXXXXXXXXXXXXXXXXXXXX.XXXXX.XXXXX...
output:
-1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1011th words differ - expected: '2203', found: '2204'
Test #19:
score: 0
Wrong Answer
time: 818ms
memory: 67596kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1002nd words differ - expected: '420525', found: '420529'
Test #20:
score: 0
Wrong Answer
time: 572ms
memory: 79992kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1003rd words differ - expected: '2000', found: '2002'
Test #21:
score: 0
Wrong Answer
time: 433ms
memory: 30740kb
input:
1000 1000 ...../\..../.\......//././/./\\./../..\/.......\\.\.....\\\\//.\.../.\....\...\../././../\...
output:
1 1 1 1 1 -1 -1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 1 -1 -1 1 1 ...
result:
wrong answer 1006th words differ - expected: '9', found: '2'
Test #22:
score: 0
Wrong Answer
time: 532ms
memory: 30736kb
input:
1000 1000 ......\...................../................................................................
output:
1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
wrong answer 1007th words differ - expected: '8', found: '2'
Test #23:
score: 0
Wrong Answer
time: 482ms
memory: 30736kb
input:
1000 1000 /............................................................................................
output:
-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
wrong answer 1001st words differ - expected: '999002', found: '2'
Test #24:
score: 0
Wrong Answer
time: 365ms
memory: 21908kb
input:
700 1000 /.............................................................................................
output:
-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
wrong answer 1001st words differ - expected: '489302', found: '2'
Test #25:
score: 0
Wrong Answer
time: 494ms
memory: 30668kb
input:
1000 1000 #.....#\/................\..#\#\\/...../.....#..\........#.\..#\...\.\........\/../../...\...
output:
-1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 -1 1 1 1 1 ...
result:
wrong answer 1009th words differ - expected: '25', found: '2'
Test #26:
score: 0
Wrong Answer
time: 519ms
memory: 38572kb
input:
1000 1000 .........X.\........\.......#..X............/#....\........./.............X.......X..........
output:
1 1 1 1 1 1 1 1 1 -1 1 -1 1 1 1 1 1 1 1 1 -1 1 1 1 1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 1...
result:
wrong answer 1010th words differ - expected: '62', found: '46'
Test #27:
score: 0
Wrong Answer
time: 628ms
memory: 38928kb
input:
1000 1000 ...../\\./.X.......X/..../../\.../.X..\X..........\...\..\.X/XX..../.X.....\...X...../XX.....
output:
1 1 1 1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 -1 1 1 -1 -1 1 1 1 -1 1 -1 1 1 -1 -1 1 1 1 ...
result:
wrong answer 1006th words differ - expected: '203', found: '2'
Test #28:
score: 0
Wrong Answer
time: 823ms
memory: 68264kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1002nd words differ - expected: '964933', found: '419466'
Test #29:
score: 0
Wrong Answer
time: 809ms
memory: 72724kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1003rd words differ - expected: '990625', found: '363133'
Test #30:
score: 0
Wrong Answer
time: 856ms
memory: 108676kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1002nd words differ - expected: '886109', found: '129082'
Test #31:
score: 0
Wrong Answer
time: 925ms
memory: 76580kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1002nd words differ - expected: '547503', found: '416765'
Test #32:
score: 0
Wrong Answer
time: 789ms
memory: 75868kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1010th words differ - expected: '831504', found: '521368'
Test #33:
score: 0
Wrong Answer
time: 914ms
memory: 39112kb
input:
1000 1000 \.XXX/\X..X\XXXX.XXXXX.X.X.X/X.\XX.XX.\XXX.XXXXX\X\.XX.XX\XX/X.X.XXXXXXXXXXX.X\XXXXXXXXX/....
output:
-1 1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -...
result:
wrong answer 1005th words differ - expected: '425', found: '3555'
Test #34:
score: 0
Wrong Answer
time: 987ms
memory: 39076kb
input:
1000 1000 X..XXXXX.XXXXXXX.XXXXX.X.X.XXXXXXX.XX.XXXX.XXX.XXXXX.X.XXXXXXX.X.XXXXXXX..XX.XXXXXXXXXXX.....
output:
-1 1 1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 1 -1 ...
result:
wrong answer 1007th words differ - expected: '936', found: '2401'
Test #35:
score: 0
Wrong Answer
time: 1284ms
memory: 102932kb
input:
1000 1000 .XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
wrong answer 1003rd words differ - expected: '999506', found: '1466334'