921519_10318.cpp

ACM 第10318題 Solve It

#include <stdio.h>

#define INFINITE 100

/* global variable */
int r, c;
int depth;
int panel[5][5] = {0};
int s[3][3];			/* switch pattern when button pressed */
int b;					/* current best time */
int buf[5*5];
int index;
int temp[5*5];

/* function prototype */
void pan(int);			/* DFS recursive function */
void pressButton(int);
int stop(int);

int main()
{
  /* local variable */
  int i, j;
  char t[5];
  int cases = 1;

  /* freopen( "10318.in", "r", stdin ); */
  
  scanf( "%d %d", &r, &c );
  while( r!= 0 ){
    /* initialize */
	depth = r*c;
	b = INFINITE;
	index = 0;
	/* read in */
	for( i=0; i< 3; i++ ){
	  scanf( "%s", &t );
	  for( j=0; j< 3; j++ ){
		if( t[j] == '*' )
		  s[i][j] = 1;
		else
		  s[i][j] = 0;
	  }
	}	
	/* brute-force(recursive DFS) */
	pan(1);
	
	/* print out */
	printf( "Case #%d\n", cases );
	if( b==INFINITE )
	  printf( "Impossible." );
	else
	  for( i=0; i< b; i++ )
		printf( "%d ", buf[i] );
	printf( "\n" );	
	/* updata data*/
	for( i=0; i< r; i++ )
	  for( j=0; j<c; j++ )
		panel[i][j] = 0;
	cases++;
	scanf( "%d %d", &r, &c );
  }
  return 0;
}

void pan(int d)
{
  int i, j;

  if(d<=depth){
	/* condition 1: unpress button */
	pan(d+1);
	/* conditino 2: pressed button */
	pressButton(d);
	temp[index++] = d;
	i = stop(d); 
	if(i==0){
	  if(index< b)
		pan(d+1);
	}
	else if(i==1){
	  if(index< b){
		b = index;
		for( j=0; j< b; j++ )
		  buf[j] = temp[j];
	  } 
	}
	/* recover original state of panel */
	pressButton(d);
	index--;
  }
}

void pressButton(int k)
{
  int i, j;
  int x, y;
  
  k--;
  x= k/c;
  y= k%c;

  /* start form upper left */
  x--;
  y--;
  for( i=0; i< 3; i++, x++, y-=3 ){
	for( j=0; j< 3; j++, y++ )
	  if( x >=0 && y >=0 && x< r && y< c )
		if(s[i][j]==1){
		  if(panel[x][y]==0)
			panel[x][y]=1;
		  else
			panel[x][y]=0;
		}
  }
}

/* return 1 present complete, 2 present wrong, 0 present don't stop */
int stop(int d)
{
  int i, j, t;
  int count = 0;
  int x;

  x= (d--)/c;
  
  /* check state of every button */
  /* t= x-i */
  for( i=0, t=x; i< r; i++, t-- )
	for( j=0; j< c; j++ ){
	  if(panel[i][j]==1)
		count++;
	  else
		if( t >1 )
		  return 2;
	}

  if(count< depth)
	return 0;
  else
	return 1;
}