【wikioi】1108ブロックゲーム(シミュレーション)

http://wikioi.com/problem/1108/
この問題は少し変態です.彼はポリシーがないからです.
それともこの問題はリアルタイムではないですか?とにかくこの問題は変態です.同じ時間帯にすべての行列の斜線を同時に解消します.!!!!!
直接シミュレーションでこれらの列を全部見つければいいです.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getnum()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline int getnum() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



const int fx[4]={1, 1, 0, -1}, fy[4]={0, 1, 1, 1}, N=70;

int n, m, vis[N][N], flag;

char a[N][N];

inline const bool cmp(const char &a, const char &b, const char &c) { if(a==b && b==c && a!=' ') return true; return false; }

inline void lian(int x, int y, const int &i, const char &c) { for(x+=fx[i], y+=fy[i]; x>=0 && x<n && y>=0 && y<m && a[x][y]==c; x+=fx[i], y+=fy[i]) vis[x][y]=1; }

inline void xiao(const int &x, const int &y) {

	int x1, x2, y1, y2;

	rep(i, 4) {

		x1=x+fx[i]; y1=y+fy[i];

		x2=x1+fx[i]; y2=y1+fy[i];

		if(x2>=0 && x2<n && y2>=0 && y2<m && cmp(a[x][y], a[x1][y1], a[x2][y2])) {

			lian(x2, y2, i, a[x][y]);

			vis[x][y]=vis[x1][y1]=vis[x2][y2]=1;

			flag=1;

		}

	}

}

inline void clean() {

	CC(vis, 0); flag=0;

	rep(i, n) rep(j, m) xiao(i, j);

	if(flag) rep(i, n) rep(j, m) if(vis[i][j]) a[i][j]=' ';

}

inline void fix() {

	int k;

	rep(j, m) {

		k=n;

		for(int i=n-1; i>=0; --i) if(a[i][j]!=' ') a[--k][j]=a[i][j];

		while(k) a[--k][j]=' ';

	}

}

int main() {

	read(n); read(m);

	rep(i, n) scanf("%s", a[i]);

	while(1) {

		clean(); fix();

		if(!flag) break;

	}

	rep(i, n) printf("%s
", a[i]);

	return 0;

}

 
 
 
 
テーマ記述Description
    赤(R)、緑(G)、青(B)、黒(A)、白(W)の5色の方形があります.3より大きい色のすべてのブロックを消去します.消去プロセスは、同じ直線上(横、縦、斜線)と同じ色の連続が3以上のブロックを同時に消去します.消去中、同じブロックは異なる方向で繰り返し使用されてもよい.ブロックが消去された後、上のブロックは自動的に落下し、消去できなくなるまで消去を繰り返します.
Input Descriptionを入力します.
入力ファイルgame.inフォーマット:第一行M N、以下M＊Nのアルファベットマトリックスです.
例えば、5＊5のブロックが設けられ、そのブロックの分布は以下の通りである.
R
R
R
A
A
 
W
R
A
A
W
A
W
B
A
B
W
R
B
W
W
B
B
W
W
A
出力記述Output Description
出力ファイルgame.outは、消去可能なすべてのブロックを消去した後、残りのブロック情報を出力する必要があります.
サンプル入力Sample Input
game.in:
5
RRRAA
WRAAW
AWBAB
WRBW
BBWWA
 
サンプル出力Sample Output
Game.out:
             A
WRA  W
AWB   B
WRBW
BBWWA
 
データ範囲とヒントData Size&Hit