## 10318 - Security Panel

Moderator: Board moderators

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

### 10318 - Security Panel

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;
int light_button, grid, step, ans;
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
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" to "light" etc.
Hope it hopes.

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

Code: Select all

``Here code``