QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #361579 | #6305. Chinese Checker | Zxc200611# | WA | 20ms | 3668kb | C++14 | 2.6kb | 2024-03-23 11:42:38 | 2024-03-23 11:42:38 |
Judging History
answer
/*
跳棋棋盘上有一些跳棋，可以选一个跳棋 x 跳若干步，对每个跳棋求出它能跳到棋盘上哪些位置。
*/
#include<bits/stdc++.h>
using namespace std;
// map 17*17
const int mpl=17;
pair<int,int> mph[]={
{0 ,-1},
{13,13},{12,13},{11,13},{10,13},
{5 ,17},{5 ,16},{5 ,15},{5 ,14},{5 ,13},
{4 ,13},{3 ,13},{2 ,13},{1 ,13},
{5 ,8 },{5 ,7 },{5 ,6 },{5 ,5 }
};
struct Edge
{
int ex,ey;
int ty;
};
int mp[20][20];
int n;
const int dir[3][2]={{1,0},{0,1},{1,-1}};
vector<Edge> t[20][20];
int vis[20][20];
pair<int,int> transform(int px,int py)
{
if(px>= 5&&px<= 9) py-=(9-px);
if(px>=14&&px<=17) py+=4;
return make_pair(5+px-py,4+py);
}
int dfs(int x,int y)
{
int res=1;
vis[x][y]=1;
for(Edge e:t[x][y])
{
if(vis[e.ex][e.ey])
continue;
res+=dfs(e.ex,e.ey);
}
return res;
}
int calc(int sx,int sy)
{
for(int i=1;i<=mpl;i++)
{
for(int j=1;j<=mpl;j++)
{
t[i][j].clear();
vis[i][j]=0;
}
}
for(int i=1;i<=mpl;i++)
{
for(int j=1;j<=mpl;j++)
{
if(mp[i][j]!=1||(i==sx&&j==sy))
continue;
for(int d=0;d<3;d++)
{
int ux=i,uy=j,vx=i,vy=j;
for(int k=1;k<=mpl;k++)
{
ux-=dir[d][0],uy-=dir[d][1];
if(ux<1||ux>mpl||uy<1||uy>mpl||mp[ux][uy]==-1)
break;
vx+=dir[d][0],vy+=dir[d][1];
if(vx<1||vx>mpl||vy<1||vy>mpl||mp[vx][vy]==-1)
break;
if(mp[ux][uy]==0) t[vx][vy].push_back((Edge){ux,uy,mp[vx][vy]});
// cout<<"("<<vx<<","<<vy<<") -> ("<<ux<<","<<uy<<") ty="<<mp[vx][vy]<<endl;
if(mp[vx][vy]==0) t[ux][uy].push_back((Edge){vx,vy,mp[ux][uy]});
// cout<<"("<<ux<<","<<uy<<") -> ("<<vx<<","<<vy<<") ty="<<mp[ux][uy]<<endl;
if(mp[ux][uy]||mp[vx][vy])
break;
}
}
}
}
return dfs(sx,sy)-1;
}
int main()
{
int T;
cin>>T;
for(int _=1;_<=T;_++)
{
for(int i=1;i<=mpl;i++)
{
for(int j=1;j<=mpl;j++)
mp[i][j]=-1;
}
for(int i=1;i<=mpl;i++)
{
for(int j=mph[i].first;j<=mph[i].second;j++)
mp[i][j]=0;
}
cin>>n;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
pair<int,int> p=transform(x,y);
// cout<<x<<" "<<y<<" -> "<<p.first<<" "<<p.second<<endl;
mp[p.first][p.second]=1;
}
// for(int i=1;i<=mpl;i++)
// {
// for(int j=1;j<=mpl;j++)
// cout<<("#.O"[mp[i][j]+1])<<" ";
// cout<<endl;
// }
int ans=0;
for(int i=1;i<=mpl;i++)
{
for(int j=1;j<=mpl;j++)
{
if(mp[i][j]==1)
{
int res=calc(i,j);
// cout<<"("<<i<<","<<j<<") : "<<res<<endl;
ans+=res;
}
}
}
cout<<ans<<'\n';
}
}
/*
2
9 4
9 6
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3556kb
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: 20ms
memory: 3668kb
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:
223 397 177 550 375 213 168 53 294 90 1 128 108 62 25 184 373 294 18 235 81 186 256 24 119 216 272 441 172 81 253 290 33 7 109 176 391 287 65 171 251 64 18 124 89 180 38 144 336 138 175 303 0 107 74 53 28 13 67 159 177 34 434 165 202 12 53 0 282 111 107 411 8 421 87 116 59 307 59 28 501 380 6 205 93...
result:
wrong answer 1st numbers differ - expected: '190', found: '223'