QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#328338 | #833. Cells Blocking | hy233 | TL | 1ms | 3912kb | C++14 | 1.6kb | 2024-02-15 19:18:44 | 2024-02-15 19:18:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3005;
const int inf=1e9;
inline int rd()
{
int x=0; bool f=1;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())
if(ch=='-') f=0;
for(;ch>='0'&&ch<='9';ch=getchar())
x=x*10+(ch^48);
return f?x:-x;
}
int n,m;
char s[N][N];
bool gd[N][N];
int col[N][N];
void dfs(int x,int y)
{
if(x>n||y>m) return;
if(s[x][y]=='*') return;
dfs(x+1,y);
dfs(x,y+1);
if(gd[x+1][y]||gd[x][y+1])
gd[x][y]=1;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
gd[n][m]=(s[n][m]=='.');
dfs(1,1);
int siz=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='.')
siz++;
if(!gd[1][1])
{
printf("%lld\n",1ll*siz*(siz-1)/2);
return 0;
}
int x=1,y=1;
while(x!=n||y!=m)
{
col[x][y]=1;
if(gd[x+1][y])
x++;
else
y++;
}
col[n][m]=1;
ll ans=0;
x=1,y=1;
while(x!=n||y!=m)
{
if(col[x][y])
siz--,ans+=siz,col[x][y]=2;
if(gd[x][y+1])
y++;
else
x++;
}
siz--; ans+=siz; col[n][m]=2;
x=1,y=1;
int cnt=0;
while(x!=n||y!=m)
{
cnt++;
assert(cnt<=n+m+5);
if(!col[x][y])
{
int xx=x+1,yy=y-1;
while(!gd[xx][yy])
xx++,yy--;
int tx=xx,ty=yy;
while(tx!=1||ty!=1)
{
if(col[tx][ty]==1)
ans++;
if(gd[tx-1][ty])
tx--;
else
ty--;
}
tx=xx,ty=yy;
while(tx!=n||ty!=m)
{
if(gd[tx][ty+1])
ty++;
else
tx++;
if(col[tx][ty]==1)
ans++;
}
}
if(gd[x][y+1])
y++;
else
x++;
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3912kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3820kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
5 5 *.... .*.*. ***** *.*** ..*..
output:
66
result:
ok 1 number(s): "66"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
10 10 ...***.*.. **...*.*** ...***.*.. .**...*.*. .*****..*. ..*.****.* .**...**** ..*..*.*.* *.*.**.... ....**...*
output:
1378
result:
ok 1 number(s): "1378"
Test #6:
score: -100
Time Limit Exceeded
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................