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 stupidjohn at 2010-05-28 07:58:49 on Problem 1753
In Reply To:居然WA是因为Impossible 打错,无线汗~~~ Posted by:stupidjohn at 2010-05-26 23:45:47
// POJ 1753
#include<iostream>
using namespace std;
int direction[4][2]={1,0,0,1,0,-1,-1,0};
int bnumber;
char map[4][4];
int clip[16];
int clips;
int isin(int x,int y)
{
	return (x>=0&&x<4&&y>=0&&y<4);
}
int min(int a,int b)
{
	return a<b?a:b;
}
void work()
{
	int i,tclip=0;
	for(i=0;i<16;i++)
	if(clip[i]) 
	{
		tclip++;
	}
	clips=min(clips,tclip);
}
void change(int x,int y)
{
	if(map[x][y]=='b'){map[x][y]='w';bnumber--;return;}
	else{map[x][y]='b';bnumber++;}
}
void run(int n)
{
	int i,x,y,newx,newy;
	if(n>16) return;
	if(bnumber==0||bnumber==16) work();
	if(n>15) return;
	x=n/4;y=n%4;
	clip[n]=1;
	change(x,y);
	for(i=0;i<4;i++)
	{
		newx=x+direction[i][0];
		newy=y+direction[i][1];
		if(isin(newx,newy))
		{
			change(newx,newy);
		}
	}
	run(n+1);
	change(x,y);
	for(i=0;i<4;i++)
	{
		newx=x+direction[i][0];
		newy=y+direction[i][1];
		if(isin(newx,newy))
		{
			change(newx,newy);
		}
	}
	clip[n]=0;
	run(n+1);
}
int main()
{
	int i,j;
	for(i=0;i<16;i++)
	clip[i]=0;
	clips=100;
	bnumber=0;
	for(i=0;i<4;i++)
	for(j=0;j<4;j++)
	{
		cin>>map[i][j];
		if(map[i][j]=='b') bnumber++;
	}
	if(bnumber==0||bnumber==16)
		cout<<0<<endl;
	else
	{
		run(0);
		if(clips==100) cout<<"Impossible"<<endl;
		else cout<<clips<<endl;
	}
	return 1;
}



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