2012年南海初中竞赛 蚂蚁

2012年南海初中竞赛 蚂蚁

题目

解题思路

有技巧的“模拟”

代码

#include<cstdio>
#include<iostream>
#include<string>
using namespace std; 
const int maxx=101,maxa=4001,x[4]={0,1,0,-1},y[4]={1,0,-1,0}; 
int n,xx[maxx],yy[maxx],ans,now[maxx],t[maxx]; string s; 
int main()
{scanf("%d",&n); cin>>s; for (int i=1;i<=n;i++){scanf("%d%d",&xx[i],&yy[i]); xx[i]*=2; yy[i]*=2; if (s[i-1]=='N') t[i]=0; else if (s[i-1]=='E') t[i]=1; elseif (s[i-1]=='S') t[i]=2; elseif (s[i-1]=='W') t[i]=3; }for (int i=1;i<=n;i++) now[i]=1;//now来记录当前的状态，1表示还未消失，2表示准备消失，3表示已消失for (int i=1;i<maxa;i++)//因为可以走0.5步，所以要先乘2，避免小数，走也要走4000步{for (int j=1;j<=n;j++) xx[j]+=x[t[j]],yy[j]+=y[t[j]];//每个点都移动for (int j=1;j<n;j++){if (now[j]==3) continue; for (int k=j+1;k<=n;k++)//两点碰撞{if (now[k]==3) continue; if (xx[j]==xx[k]&&yy[j]==yy[k]) { now[j]=now[k]=2;}//如果直接记录为3，那么多个点一起碰撞，就无法解决了}}for (int j=1;j<=n;j++)if (now[j]==2) now[j]=3; }for (int i=1;i<=n;i++)if (now[i]==1) ans++; //记录未消失的点                                                                                                                                                                                                                                                   printf("%d",ans); 
}