裏紙

ほぼ競プロ、たまに日記

AOJ 2311 - Dessert Witch

・問題
Dessert Witch | Aizu Online Judge

ようは貪欲にやるオセロ。問題文に書かれていることを素直にシミュレーションすれば出来る。久々にこういうただただ書くのがめんどくさいやつをやった。

・実装(C++)

#include <cstdio>
#include <iostream>
using namespace std;

//真上から時計回り
int dx[8]={0,1,1,1,0,-1,-1,-1};
int dy[8]={1,1,0,-1,-1,-1,0,1};

//fの状況でx,yにcを置いた時に、ひっくり返せる個数
int revnums(char f[8][9], int x, int y, char c, int flag){
  int ret=0;

  char e_cookie;
  if(c=='o') e_cookie='x';
  else e_cookie='o';

  if(f[x][y]=='.'){ //クッキーがないのでおけるかどうか調べる
    //8方向に対して
    for(int i=0; i<8; ++i){
      int r=1;

      while(0<=x+r*dx[i] && x+r*dx[i]<8 && 0<=y+r*dy[i] && y+r*dy[i]<8){
        char focus=f[x+r*dx[i]][y+r*dy[i]];
        if(focus==c){ //自分のクッキー
          //間にある敵クッキーがひっくり返せる個数になる

          //実際にひっくり返す
          if(flag==1){
            //まず置く
            f[x][y]=c;
            //ひっくり返す
            for(int j=1; j<r; ++j){
              f[x+j*dx[i]][y+j*dy[i]] = c;
            }
          }

          ret+=r-1;
          break;
        }
        else if(focus==e_cookie){ //相手のクッキーがある
          r++;
        }
        else{ //どのクッキーもなかった
          break;
        }
      }

    }

  }
  return ret;
}

bool charlotte(char f[8][9]){
  int rev=0;
  int x=-1,y=-1;
  char c='x';
  //右下から
  for(int i=7; i>=0; --i){
    for(int j=7; j>=0; --j){
      int tmp=revnums(f,i,j,c,0);
      if(rev<tmp){
        rev=tmp;
        x=i;
        y=j;
      }
    }
  }

  //置ける場所があったらその場所に実際に置いて変更
  if(x>=0){
    revnums(f,x,y,c,1);
  }

  return (rev>0);
}

bool tomoe(char f[8][9]){
  int rev=0;
  int x=-1,y=-1;
  char c='o';
  //左上から
  for(int i=0; i<8; ++i){
    for(int j=0; j<8; ++j){
      int tmp=revnums(f,i,j,c,0);
      if(rev<tmp){
        rev=tmp;
        x=i;
        y=j;
      }
    }
  }

  //置ける場所があったらその場所に実際に置いて変更
  if(x>=0){
    revnums(f,x,y,c,1);
  }

  return (rev>0);
}

void print_field(char f[8][9]){
  for(int i=0; i<8; ++i){
    for(int j=0; j<8; ++j){
      printf("%c", f[i][j]);
    }
    printf("\n");
  }
}

int main(){
  char f[8][9];

  for(int i=0; i<8; ++i)
  for(int j=0; j<8; ++j)
  scanf(" %c", &f[i][j]);

  bool c=true, t=true;
  while(c || t){
    t=tomoe(f);
    c=charlotte(f);
  }

  print_field(f);
}