QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #359845 | #6305. Chinese Checker | Siilhouette | WA | 3ms | 3852kb | C++14 | 4.7kb | 2024-03-20 21:54:43 | 2024-03-20 21:54:43 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,tim;
struct Node{
int x,y;
Node(){}
Node(int _x,int _y):x(_x),y(_y){}
}a[1010];
struct Graph{
int bias=50;
int a[100][100];
inline void set(int x,int y,int z){
// cout<<"set "<<x<<" "<<y<<" "<<z<<endl;
a[x+bias][y+bias]=z;}
inline bool valid(int x,int y){return a[x+bias][y+bias];}
inline int getv(int x,int y){ return a[x+bias][y+bias]; }
inline void init(){ memset(a,0,sizeof(a)); }
}valid,c,vis;
queue<Node>q;
inline bool update(int edx,int edy)
{
if(vis.getv(edx,edy)==tim)return 0;
vis.set(edx,edy,tim);
q.push(Node(edx,edy));
return 1;
}
inline int bfs(Node st)
{
tim++;int res=0;
vis.set(st.x,st.y,tim);
q.push(st);
while(q.size())
{
Node pos=q.front();
q.pop();
bool v=1;
for(int i=1;;i++)
{
if(!valid.getv(pos.x+i,pos.y))break;
if(c.getv(pos.x+i,pos.y))
{
v=1;
for(int j=1;j<=i;j++)
if(!valid.getv(pos.x+i+j,pos.y)||c.getv(pos.x+i+j,pos.y)){ v=0;break; }
if(v)res+=update(pos.x+i*2,pos.y);
break;
}
}
for(int i=-1;;i--)
{
if(!valid.getv(pos.x+i,pos.y))break;
if(c.getv(pos.x+i,pos.y))
{
v=1;
for(int j=-1;j>=i;j--)
if(!valid.getv(pos.x+i+j,pos.y)||c.getv(pos.x+i+j,pos.y)){ v=0;break; }
if(v)res+=update(pos.x+i*2,pos.y);
break;
}
}
for(int i=1;;i++)
{
if(!valid.getv(pos.x,pos.y+i))break;
if(c.getv(pos.x,pos.y+i))
{
v=1;
for(int j=1;j<=i;j++)
if(!valid.getv(pos.x,pos.y+i+j)||c.getv(pos.x,pos.y+i+j)){ v=0;break; }
if(v)res+=update(pos.x,pos.y+i*2);
break;
}
}
for(int i=-1;;i--)
{
if(!valid.getv(pos.x,pos.y+i))break;
if(c.getv(pos.x,pos.y+i))
{
v=1;
for(int j=-1;j>=i;j--)
if(!valid.getv(pos.x,pos.y+i+j)||c.getv(pos.x,pos.y+i+j)){ v=0;break; }
if(v)res+=update(pos.x,pos.y+i*2);
break;
}
}
for(int i=1;;i++)
{
if(!valid.getv(pos.x-i,pos.y+i))break;
if(c.getv(pos.x-i,pos.y+i))
{
v=1;
for(int j=1;j<=i;j++)
if(!valid.getv(pos.x-i-j,pos.y+i+j)||c.getv(pos.x-i-j,pos.y+i+j)){ v=0;break; }
if(v)res+=update(pos.x-i*2,pos.y+i*2);
break;
}
}
for(int i=-1;;i--)
{
if(!valid.getv(pos.x-i,pos.y+i))break;
if(c.getv(pos.x-i,pos.y+i))
{
v=1;
for(int j=-1;j>=i;j--)
if(!valid.getv(pos.x-i-j,pos.y+i+j)||c.getv(pos.x-i-j,pos.y+i+j)){ v=0;break; }
if(v)res+=update(pos.x-i*2,pos.y+i*2);
break;
}
}
}
return res;
}
signed main()
{
for(int i=1;i<=13;i++)
for(int j=1;i+j<=14;j++)
valid.set(i,j,1);
for(int i=6;i<=9;i++)
for(int j=1;j<=i-6+1;j++)
valid.set(i,1-j,1);
for(int i=6;i<=9;i++)
for(int j=1;j<=9;j++)
valid.set(i,j,1);
for(int i=0;i>=-3;i--)
for(int j=9;j>=-i+6;j--)
valid.set(i,j,1);
int T;
scanf("%d",&T);
while(T--)
{
c.init();
scanf("%d",&n);
for(int i=1,x,y;i<=n;i++)
{
scanf("%d%d",&x,&y);
int _x=14-x,_y;
if((_x>=1&&_x<=5)||(_x>=10&&_x<=13))
_y=y;
else if(_x>=6&&_x<=9)
{
if(y<=(_x-5))_y=6-_x+y-1;
else _y=y-(_x-5);
}
else _y=6-x+y-1;
c.set(_x,_y,1);
a[i].x=_x,a[i].y=_y;
// cout<<"x y "<<_x<<" "<<_y<<endl;;
}
int ans=0;
for(int i=1;i<=n;i++)
{
// cout<<a[i].x<<" "<<a[i].y<<endl;
c.set(a[i].x,a[i].y,0);
// cout<<"bfs "<<bfs(a[i])<<endl;
ans+=bfs(a[i]);
c.set(a[i].x,a[i].y,1);
}
printf("%d\n",ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3836kb
input:
5 1 1 1 2 1 1 2 1 2 9 4 9 6 10 1 1 2 1 2 2 3 1 3 2 3 3 4 1 4 2 4 3 4 4 10 1 1 2 1 2 2 5 7 3 2 3 3 4 1 4 2 4 3 4 4
output:
0 1 2 6 13
result:
ok 5 number(s): "0 1 2 6 13"
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3852kb
input:
100 81 1 1 16 1 11 4 13 8 12 3 12 12 11 1 4 2 9 5 8 10 5 5 9 7 3 2 14 1 7 11 13 7 10 2 8 3 9 8 10 6 12 10 6 7 11 2 7 3 13 12 8 6 17 1 10 5 5 12 13 9 13 1 9 4 5 10 11 8 13 4 5 4 9 1 7 8 5 6 13 13 5 1 9 3 8 8 8 5 13 2 13 5 11 3 9 2 6 4 3 3 8 2 13 11 8 7 5 7 6 10 11 9 10 3 11 10 6 3 7 1 4 4 15 2 7 2 3 ...
output:
199 348 167 453 355 217 180 40 294 89 1 121 106 61 25 175 360 294 18 215 90 188 256 24 104 219 274 408 172 82 200 259 33 7 101 170 380 284 56 166 267 48 18 133 79 169 38 142 309 117 175 265 0 108 75 54 31 13 58 152 168 34 420 176 201 12 48 0 237 106 108 369 8 342 75 107 55 332 57 28 483 344 6 191 93...
result:
wrong answer 1st numbers differ - expected: '190', found: '199'