这是一个发问帖,请勿将以下 AC Code 直接提交,以免判作弊。
这是原代码:
#pragma gcc optimize(2)
#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
#define maxn 10010
#define inf 2147483647
using namespace std;
int k,n,dx[maxn],dy[maxn],xm=0,ym=0,t=100,flag=0;
bool vis[maxn][maxn];
inline int read(){
int x=0,f; char ch=0;
while(!isdigit(ch)) f=(ch=='-'?-1:1),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
inline void print(int x){
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+48);
}
inline void write(int x){print(x);putchar('\n');}
queue<int> qwq,pwp;
void bfs(){
vis[t][t-1]=0;
vis[t][t+1]=0;
vis[t-1][t]=0;
vis[t+1][t]=0;
for(int i=-xm+t;i<=xm+t;i++){
for(int j=-ym+t;j<=ym+t;j++){
vis[i][j]=0;
}
}
for(int i=1;i<=n;i++){
qwq.push(dx[i]+t);
pwp.push(dy[i]+t);
vis[dx[i]+t][dy[i]+t]=1;
}
while(!qwq.empty()){
int ux=qwq.front();
int uy=pwp.front();
qwq.pop(),pwp.pop();
vis[ux][uy]=1;
for(int l=1;l<=n;l++){
int xx=ux+dx[l],yy=uy+dy[l];
if(xx>=-xm+t&&xx<=xm+t&&yy>=-ym+t&&yy<=ym+t&&!vis[xx][yy]){
vis[xx][yy]=1;
qwq.push(xx);
pwp.push(yy);
if(vis[t-1][t]&&vis[t+1][t]&&vis[t][t-1]&&vis[t][t+1]){
flag=1;
break;
}
}
}
}
return;
}
signed main(){
k=read();
while(k--){
n=read();
xm=0,ym=0;
for(int i=1;i<=n;i++){
dx[i]=read(),dy[i]=read();
xm=max(abs(dx[i]),xm),ym=max(abs(dy[i]),ym);
}
flag=0;
bfs();
if(flag)cout<<"TAK"<<endl;
else cout<<"NIE"<<endl;
};
return 0;
}
90pts,T一个点。
在同学微改之下 A 了。
#pragma gcc optimize(2)
#include <iostream>
#include <algorithm>
#include <queue>
#define int long long
#define maxn 10010
#define inf 2147483647
using namespace std;
int k,n,dx[maxn],dy[maxn],xm=0,ym=0,t=100,flag;
bool vis[maxn][maxn];
inline int read(){
int x=0,f; char ch=0;
while(!isdigit(ch)) f=(ch=='-'?-1:1),ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
inline void print(int x){
if(x<0) x=-x,putchar('-');
if(x>9) print(x/10);
putchar(x%10+48);
}
inline void write(int x){print(x);putchar('\n');}
queue<int> qwq,pwp;
void bfs(){
for(int i=-xm+t;i<=xm+t;i++){
for(int j=-ym+t;j<=ym+t;j++){
vis[i][j]=0;
}
}
for(int i=1;i<=n;i++){
qwq.push(dx[i]+t);
pwp.push(dy[i]+t);
vis[dx[i]+t][dy[i]+t]=1;
}
while(!qwq.empty()){
int ux=qwq.front();
int uy=pwp.front();
qwq.pop(),pwp.pop();
vis[ux][uy]=1;
for(int l=1;l<=n;l++){
int xx=ux+dx[l],yy=uy+dy[l];
if(xx>=-xm+t&&xx<=xm+t&&yy>=-ym+t&&yy<=ym+t&&!vis[xx][yy]){
vis[ux+dx[l]][uy+dy[l]]=1;
qwq.push(ux+dx[l]);
pwp.push(uy+dy[l]);
}
if(vis[t-1][t]&&vis[t+1][t]&&vis[t][t-1]&&vis[t][t+1]){
flag=1;
break;
}
}
}
if(vis[t-1][t]&&vis[t+1][t]&&vis[t][t-1]&&vis[t][t+1]){
flag=1;
return;
}
}
signed main(){
k=read();
while(k--){
n=read();
for(int i=1;i<=n;i++){
dx[i]=read(),dy[i]=read();
xm=max(abs(dx[i]),xm),ym=max(abs(dy[i]),ym);
}
flag=0;
bfs();
if(flag)cout<<"TAK"<<endl;
else cout<<"NIE"<<endl;
};
return 0;
}
蒟蒻不解为何会这样。
另:
管理大大如看见提交中有如上相同代码,不是抄袭,谢谢。