题解：P13390 [GCJ 2010 #1A] Rotate

· · 题解

这道题就是一道纯模拟题。

先定义两个二维字符数组。

char a[1010][1010],b[1010][1010];

再输入 b 数组。

然后将其旋转，转移方程如下：

a[j][n-i+1]=b[i][j];
//i表示第i行，j表示第j列，n表示一个n*n的图

然后就是“自由落体”，我们一列一列来处理。

  1. 定义两个指针都从大到小。

  2. 判断第一个指针是否有没有人下棋，如果有，指针就减小。

  3. 判断第二个指针是否有没有人下棋，如果没有，指针就减小。

  4. 如果两个指针都不用往减小，就可以将第二个指针所指向的棋子，移到第一个指针所指向的位置，然后两个指针都减小。

for(int j=1;j<=n;j++)//一列列处理
{
    for(int i=n,l=n;l>=1;)//两个指针
    {
        if(a[l][j]!='.'&&a[i][j]=='.')
        {
            a[i][j]=a[l][j],a[l][j]='.';
            //将第二个指针所指向的棋子，移到第一个指针所指向的位置
            l--,i--;    
        }
        if(a[i][j]!='.') i--;
        //第一个指针是否有没有人下棋，如果有，指针就减小
        if(a[l][j]=='.') l--;
        //第二个指针是否有没有人下棋，如果没有，指针就减小
        if(l>=i) l=i-1;
        //如果第一个指针移到第二个指针上面了，就将第二个指针移上来
    }
}

然后是判断是否能连续k个

  1. 然后可以定义两个方向数组，分别表示行和列。
int fx[8]=[1,-1,0, 0,1,-1, 1, -1];//行
int fy[8]=[0, 0,1,-1,1,-1,-1,  1];//列
  1. 然后一个个进行枚举每一个棋子，它能从任何方向连成的最大长度。

（这个时候方向数组就能起到作用了）

for(int i:1-n)
{
    for(int j:1-n)
    {
        if(a[i][j]!='.')//这里必须要有棋子
        {
            int sum=0;
            for(int f:0-7)//8个方向
            {
                int ans=1;//连成的棋子数
                while(a[i+ans*fx[f]][j+ans*fy[f]]==a[i][j])//要和原来的棋子颜色相同
                    ans++;
                sum=max(sum,ans);//求能连成的最大值
            }
        }

    }
}
  1. 枚举完这颗棋子后，判断这种颜色是否达到连续k个及以上。如果达到，然后判断颜色，标记这个颜色出现过。

最后输出。

//f表示红色，f2表示蓝色
//true出现过，false表示没有
cout<<"Case #"<</*第几轮*/<<": ";
if(f==true)
{
    if(f2==true) cout<<"Both\n";
    else cout<<"Red\n";
}
else
{
    if(f2==true) cout<<"Blue\n";
    else cout<<"Neither\n";
}