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

新手暴试47ms, 可以如何改进?

Posted by ytlau9 at 2011-01-10 14:53:58 on Problem 1753
而且如何再写短一点, 求教..

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define flip(x,y) tmp[x][y]=(tmp[x][y]=='b'? 'w' : 'b')
#define REG(i,x) for(int i=0;i<x;i++)
using namespace std;

char w[4][4],tmp[4][4];
int t[4][4];

void search(){
        REG(i,4){
                if(i>0)
                        REG(j,4)
                                if(tmp[i-1][j]=='b') t[i][j] = 1;
                REG(j,4){
                        if(t[i][j]){
                                flip(i,j);
                                if(i-1>=0)flip(i-1,j);
                                if(i+1<=3)flip(i+1,j);
                                if(j-1>=0)flip(i,j-1);
                                if(j+1<=3)flip(i,j+1);
                        }
                }
        }
}
int check(){
        int cnt = 0;
        REG(i,4)
                REG(j,4){
                        if(tmp[i][j]=='b') return 1e9;
                        if(t[i][j]) cnt++;
                }
        return cnt;
}
int main(){
        int ans = 1e9;
        REG(i,4){
                REG(j,4)
                        w[i][j] = getchar();
                getchar();
        }
        for(int i=0;i< 1<<4;i++){
                memset(t,0,sizeof(t));
                for(int S=1; S< 1<<4;S<<=1)
                        if(S&i)
                                t[0][(int)log2(S&i)] = 1;

                REG(j,4)
                        REG(k,4)
                        tmp[j][k] = w[j][k];

                search();
                if(check() < ans) ans =check();


                memset(t,0,sizeof(t));
                for(int S=1; S< 1<<4;S<<=1)
                        if(S&i)
                                t[0][(int)log2(S&i)] = 1;

                REG(j,4)
                        REG(k,4)
                        tmp[j][k] = (w[j][k]=='b'? 'w':'b');

                search();
                if(check() < ans) ans = check();

        }
        if(ans == 1e9) printf("Impossible\n");
        else printf("%d\n", ans);
        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