Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这模拟题真磨死我了~

Posted by Moon_1st at 2011-01-13 16:07:21 on Problem 1027
我滴个妈妈啊,连写加debug弄了3个小时,终于是1Y过了~贴码留念一下~
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 10;
const int M = 15;
const int px[4] = {1,-1,0,0};
const int py[4] = {0,0,1,-1};

struct node
{
    int x, y, sum;
    char c;
};

int n, sign[N][M];
char s[12][16];
bool visit[N][M];
node p[160];

void dfs(int x, int y, int& sum, const int& ct)
{
    int i, tx, ty;
    sum++;
    visit[x][y] = true;
    sign[x][y] = ct;
    if(y<p[ct].y || (y==p[ct].y && x<p[ct].x))
    {
        p[ct].x = x;
        p[ct].y = y;
    }
    for(i = 0; i < 4; i++)
    {
        tx = x + px[i];
        ty = y + py[i];
        if(tx<0 || tx>=N)  continue;
        if(ty<0 || ty>=M)  continue;
        if(!visit[tx][ty] && s[tx][ty]==p[ct].c)
            dfs(tx, ty, sum, ct);
    }
}

void Mov(int pos)
{
    int i, j, k;
    bool cv[M];
    for(i = 0; i < M; i++)
    {
        j = k = 0;
        while(k < N)
        {
            if(sign[k][i] == pos)
            {
                s[k][i] = ' ';
                k++;
            }
            else
            {
                s[j][i] = s[k][i];
                j++;
                k++;
            }
        }
        for(k = j; k < N; k++)  s[k][i] = ' ';
    }
    for(i = 0; i< M; i++)
        if(s[0][i] == ' ')
            cv[i] = true;
        else
            cv[i] = false;
    i = 0;
    for(k = 0; k < M; k++)
    {
        if(cv[k]) continue;
        else
        {
            for(j = 0; j < N; j++)
                s[j][i] = s[j][k];
            i++;
        }
    }
    for(k = i; k < M; k++)
        for(j = 0; j < N; j++)
            s[j][k] = ' ';
}

int main()
{
    int i, j, Case = 0, ct, pos, Score, t, tmp;
    freopen("data.txt", "r", stdin);
    cin >> n;
    while(n--)
    {
        Case++;
        if(Case > 1)  printf("\n");
        printf("Game %d:\n\n", Case);
        for(i = 9; i >= 0; i--)  cin >> s[i];
        Score = t = 0;
        while(1)
        {
            ct = 0;
            for(i = 0; i < 160; i++)
            {
                p[i].x = p[i].y = 20;
                p[i].sum = 0;
                p[i].c = ' ';
            }
            memset(sign, -1, sizeof(sign));
            memset(visit, false, sizeof(visit));
            for(i = 0; i < N; i++)
                for(j = 0; j < M; j++)
                {
                    if(visit[i][j])  continue;
                    if(s[i][j] == ' ')  continue;
                    p[ct].c = s[i][j];
                    dfs(i, j, p[ct].sum, ct);
                    ct++;
                }
            pos = 0;
            for(i = 0; i < ct; i++)
            {
                if(p[i].sum < p[pos].sum)  continue;
                if(p[i].sum > p[pos].sum)
                {
                    pos = i;
                    continue;
                }
                if(p[i].y<p[pos].y || (p[i].y==p[pos].y && p[i].x<p[pos].x))
                    pos = i;
            }
            if(p[pos].sum <= 1)  break;
            Mov(pos);
            t++;
            tmp = p[pos].sum - 2;
            tmp = tmp * tmp;
            Score += tmp;
            printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n", t,
                   p[pos].x+1, p[pos].y+1, p[pos].sum, p[pos].c, tmp);
        }
        if(ct == 0)  Score += 1000;
        printf("Final score: %d, with %d balls remaining.\n", Score, ct);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator