UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211425#3803. 激光mygr4518943ms108676kbC++2.9kb2024-08-11 11:54:152024-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'