97高市資訊學科能力競賽 6. 按鈕問題
作法: BY JOYBO <- 自己看唄=]
Backtracking 或 DFS
/*************************************************************/
#include<stdio.h>
#include<stdlib.h>
int N,M,a,b,MIN;
char map[10][10];
void click(int x,int y)
{
map[x][y]=1-map[x][y];
if(x-1>=0) map[x-1][y]=1-map[x-1][y];
if(x+1<N) map[x+1][y]=1-map[x+1][y];
if(y-1>=0) map[x][y-1]=1-map[x][y-1];
if(y+1<M) map[x][y+1]=1-map[x][y+1];
}
void DFS(int x,int y,int time)
{
if(y==M) ++x,y=0;
if(x==0)
{
DFS(x,y+1,time);
click(x,y);/*按下*/
DFS(x,y+1,time+1);
click(x,y);/*還原*/
}
else if(x<N)
{
if(map[x-1][y]==0) /*上面那格是開的*/
{
click(x,y); /*則按下此格*/
DFS(x,y+1,time+1);
click(x,y);
}
else DFS(x,y+1,time);
}
else
{
int a;
for(a=0;a<M;a++)
if(map[N-1][a]==0)
return;
if(time<MIN) MIN=time;
}
}
main()
{
while(scanf("%d %d",&N,&M)==2)
{
for(a=0;a<N;a++)
{
scanf("%s",&map[a]);
for(b=0;b<M;b++)
map[a][b]=(map[a][b]=='O')?0:1; /*1開 2 關*/
}
MIN=2147483647;
DFS(0,0,0);
if(MIN==2147483647) printf("Can not\n");
else printf("Minimum Steps :%d\n",MIN);
}
return 0;
}