| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
新手暴试47ms, 可以如何改进?而且如何再写短一点, 求教..
#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator