COJ 1174 Shining Gems

玩过这个游戏，这个题是判断当前局面是属于哪一种：有三个连在一块，换一个位置后有三个连着，其他情况；

思路有两种：对每一个位置枚举周围所有可能的情况，然后判断，或者对每一个位置移动前后行和列的情况进行判断；

如果使用前一种，可能遭遇大量的判断，难以保证能考虑全所有情况，代码也显得很长，后一种代码稍短，相对好写一点；

924MS，怎么没卡一下？

# include <stdio.h>

const int d[4][2] =  {{-1,0},{0,1},{1,0},{0,-1}};

int n, m, f0, f1;
char f[1005][1005];

int check(int i, int j);
void n_swap(char *x, char *y);

int main()
{
    int i, j, k, ni, nj;

    while (~scanf("%d%d", &n, &m))
    {
        for (i = 1; i <= n; ++i)
            scanf("%s", f[i]+1);

        f0 = f1 = 0;
        for (i = 1; !f0 && i <= n; ++i)
            for (j = 1; j <= m; ++j)
            {
                if (check(i,j))
                {
                    f0 = 1;
                    break;
                }
                for (k = 0; !f1 && k < 4; ++k)
                {
                    ni = i + d[k][0];
                    nj = j + d[k][1];
                    if (ni<=n && ni>=1 && nj>=1 && nj <= m)
                    {
                        n_swap(&f[ni][nj], &f[i][j]);
                        if (check(ni, nj)) f1 = 1;
                        n_swap(&f[ni][nj], &f[i][j]);
                    }
                }
            }

        if (f0) puts("Combo");
        else if (f1) puts("Enjoy It");
        else puts("Game Over");
    }

    return 0;
}

int check(int i, int j)
{
    int k, cnt = 0;
    char ch = f[i][j];

    if ((k=i-2) <= 0) k = 1;
    while (k <= n && ch != f[k][j]) ++k;
    while (cnt < 3 && k <= n && ch == f[k++][j]) ++cnt;
    if (cnt >= 3) return 1;
    cnt = 0;
    if ((k = j-2) <= 0) k = 1;
    while (k <= m && ch != f[i][k]) ++k;
    while (cnt < 3 && k <= m && ch == f[i][k++]) ++cnt;
    if (cnt >= 3) return 1;
    return 0;
}

void n_swap(char *x, char *y)
{
    char ch;

    ch = *x;
    *x = *y;
    *y = ch;
}