The Same Game

【题目类型】模拟

&题解：

写这种模拟题要看心态啊,还要有足够的时间,必须仔细读题,一定要写一步,就调试一步.

这题我没想到的就是退出循环的条件,之后问了别人才知道:只要所有联通块的节点全是1,或者全部消掉了,就break.

注意:dfs的结束条件在最上面的,所以4个方向循环的时候不用特判,dfs一定要写vis标记

&代码：

#include <cstdio>

#include <bitset>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

const int maxn= 30 +9;

string s[maxn];

int n=10,m=15,vis[maxn][maxn];

struct pn

{

    int x,y;

};

void dfs(int x,int y,char c,int& t)

{

    if(x<0||x>=n||y<0||y>=m||vis[x][y]) return;

    if(s[x][y]!=c) return;

    t++;

    vis[x][y]=1;

    for(int i=-1;i<2;i++){

        for(int j=-1;j<2;j++) if(!i^!j){

                dfs(x+i,y+j,c,t);

        }

    }

}

void dfs2(int x,int y,char c)

{

    if(x<0||x>=n||y<0||y>=m||vis[x][y]) return;

    if(s[x][y]!=c) return;

    s[x][y]='.';

    vis[x][y]=1;

    for(int i=-1;i<2;i++){

        for(int j=-1;j<2;j++) if(!i^!j){

                dfs2(x+i,y+j,c);

        }

    }

}

int K;

vector<int> vi;

bool allem(int y)

{

    for(int i=0;i<n;i++){

        if(s[i][y]!='.')

            return false;

    }

    return true;

}

void smove()

{

    //down

    for(int j=0;j<m;j++){

        for(int i=n-1;i>=0;i--){

            if(s[i][j]=='.'){

                for(int k=i;k>=0;k--){

                    if(s[k][j]!='.'){

                        swap(s[i][j],s[k][j]);

                        break;

                    }

                }

            }

        }

    }

    //left

    for(int j=0;j<m;j++){

        if(allem(j)){

            for(int k=j;k<m;k++){

                if(!allem(k)){

                    for(int i=0;i<n;i++)

                        swap(s[i][j],s[i][k]);

                    break;

                }

            }

        }

    }

}

int okw()

{

    int ans=0;

    for(int i=0;i<n;i++)

    for(int j=0;j<m;j++){

        if(s[i][j]!='.')

            ans++;

    }

    return ans;

}

int main()

{

//	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	freopen("E:1.txt","r",stdin);

//	freopen("E:2.txt","w",stdout);

    int T; cin>>T;

    while(T--){

        ll fin=0;

        for(int i=0;i<n;i++){

            cin>>s[i];

        }

        printf("Game %d:\n\n",++K);

        int KK=0;

        for(;1;){

            vi.clear();

            memset(vis,0,sizeof(vis));

            int num=0,J=0;

            pn p;

            char CC;

            for(int j=0;j<m;j++)

            for(int i=n-1;i>=0;i--) if(!vis[i][j]&&s[i][j]!='.'){

                int t=0;

                dfs(i,j,s[i][j],t);

                J++;

                if(t<=1) continue;

                vi.push_back(t);

//                if(o==5){

//                    printf("t=%d===\n",t);

//                    printf("i=%d j=%d\n",i,j);

//                }

                if(t>num){

                    CC=s[i][j];

                    p.x=i,p.y=j;

                    num=t;

                }

                else if(t==num){

                    if(j<p.y&&i>p.x){

                        CC=s[i][j];

                        p.x=i,p.y=j;

                    }

                }

            }

//            cout<<num<<endl;

//            cout<<p.x<<','<<p.y<<endl;

//            cout<<CC<<endl;

            memset(vis,0,sizeof(vis));

            if(vi.empty()||okw()==0){

                break;

            }

            dfs2(p.x,p.y,CC);

//            for(int i=0;i<n;i++){

//                cout<<s[i]<<endl;

//            }

            printf("Move %d at (%d,%d): removed %d balls of color %c, got %lld points.\n",++KK,n-p.x,p.y+1,num,CC,(ll)(num-2)*(num-2));

            fin+=(ll)(num-2)*(num-2);

            smove();

//            for(int i=0;i<n;i++){

//                cout<<s[i]<<endl;

//            }

//            for(auto i:vi)

//                cout<<i<<" ";

//            cout<<endl;

        }

        if(!okw()){

            fin+=1000;

        }

        printf("Final score: %lld, with %d balls remaining.\n",fin,okw());

        if(K!=n) puts("");

    }

	return 0;

}

巴特西

CSU 1862 The Same Game(模拟)

The Same Game

最新文章

热门文章