?? 921519_10318.cpp
字號:
#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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -