10318 - Security Panel

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Mr.south
New poster
Posts: 11
Joined: Thu Jan 25, 2007 1:45 pm

10318 - Security Panel

Post by Mr.south » Tue Feb 27, 2007 7:20 pm

well...i need a direct answer. i have no idea where i get wrong.
someone who thought he/she is one of the best programmer. help me please

#include <stdio.h>

char light[3][3];
int light_button[9], grid[5][5], step[25], ans[25];
int bound, row, column;
void initialize();
void toggle(int i, int j);
void BandB(int NowP, int depth);

int main()
{
int i, case_num = 1;

while(scanf("%d%d", &row, &column) && row != 0 && column != 0)
{
initialize();
BandB(0, 0);
printf("Case #%d\n", case_num++);
if(bound == 1000)
{
printf("Impossible.\n");
}
else
{
for(i=0;ans != -1;i++)
{
printf("%d ", (ans+1));
}
printf("\n");
}
}
}

void initialize()
{
int i, j, top = 0;
char temp;

bound = 1000;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
grid[j] = -1;
step[i*5 + j] = -1;
ans[i*5 + j] = -1;
}
}

for(i=0;i<row;i++)
{
for(j=0;j<column;j++)
{
grid[j] = 0;
}
}
for(i=0;i<9;i++)
{
light_button = 0;
}
for(i=0;i<3;i++)
{
scanf("%c", &temp);
for(j=0;j<3;j++)
{
scanf("%c", &light[j]);
if(light[j] == '*')
{
light_button[top++] = i*3 + j + 1;
}
}
}
}

void BandB(int NowP, int depth)
{
int i, j, k, light=0;
int p=NowP;

if(depth > bound) return;

for(i=0;i<row;i++)
{
for(j=0;j<column;j++)
{
if(grid[j] == 1) light++;
}
}
if(light == row*column)
{
bound = depth;
for(i=0;i<depth;i++)
{
ans = step;
}
}

i = p / column;
j = p % column;

if(i-2 >= 0)
{
for(k=0;k<column;k++)
{
if(grid[i-2][k] == 0) return;
}
}
if(p < row*column)
{
toggle(i, j);
step[depth] = p;
BandB(p+1, depth+1);
toggle(i, j);
step[depth--] = -1;
BandB(p+1, depth+1);
}
}
void toggle(int i, int j)
{
int k;

for(k=0;light_button[k]!=0;k++)
{
switch(light_button[k])
{
case 1:
if(i-1 >= 0 && j-1 >= 0 && grid[i-1][j-1] == 0) grid[i-1][j-1] = 1;
else
if(i-1 >= 0 && j-1 >= 0 && grid[i-1][j-1] == 1) grid[i-1][j-1] = 0;
break;
case 2:
if(i-1 >= 0 && grid[i-1][j] == 0) grid[i-1][j] = 1;
else
if(i-1 >= 0 && grid[i-1][j] == 1) grid[i-1][j] = 0;
break;

case 3:
if(i-1 >= 0 && j+1 < column && grid[i-1][j+1] == 0) grid[i-1][j+1] = 1;
else
if(i-1 >= 0 && j+1 < column && grid[i-1][j+1] == 1) grid[i-1][j+1] = 0;
break;

case 4:
if(j-1 >= 0 && grid[i][j-1] == 0) grid[i][j-1] = 1;
else
if(j-1 >= 0 && grid[i][j-1] == 1) grid[i][j-1] = 0;
break;
case 5:
if(grid[i][j] == 0) grid[i][j] = 1;
else
if(grid[i][j] == 1) grid[i][j] = 0;
break;
case 6:
if(j+1 < column && grid[i][j+1] == 0) grid[i][j+1] = 1;
else
if(j+1 < column && grid[i][j+1] == 1) grid[i][j+1] = 0;
break;
case 7:
if(i+1 < row && j-1 >= 0 && grid[i+1][j-1] == 0) grid[i+1][j-1] = 1;
else
if(i+1 < row && j-1 >= 0 && grid[i+1][j-1] == 1) grid[i+1][j-1] = 0;
break;
case 8:
if(i+1 < row && grid[i+1][j] == 0) grid[i+1][j] = 1;
else
if(i+1 < row && grid[i+1][j] == 1) grid[i+1][j] = 0;
break;
case 9:
if(i+1 < row && j+1 < column && grid[i+1][j+1] == 0) grid[i+1][j+1] = 1;
else
if(i+1 < row && j+1 < column && grid[i+1][j+1] == 1) grid[i+1][j+1] = 0;
break;
}
}
}

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

Post by pineapple » Sat Apr 14, 2007 11:23 pm

Mr.south,
You can see this problem don't exist PE by now,I think your code will print an extra space at the end of a line.Maybe it will lead your code to get WA.However I haven't solved it within 10S,I used backtrack which is too slow.Your programme runs very fast,so I think your algorithm accord with the request,but maybe there are some bugs in your implement.
BTW,some of the arrays are too small.it's quite dangerous,so you'd better change "light[3][3]" to "light[4][4]" etc.
Hope it hopes.

User avatar
Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj » Sun Apr 15, 2007 1:10 pm

Use

Code: Select all

Here code

Post Reply

Return to “Volume 103 (10300-10399)”