HDU 4770 Lights Against Dudely(二)
][2]) { int i,j; for(i=0;i<3;i++) { int xx=x+st[i][0]; int yy=y+st[i][1]; if(xx>0&&xx<=n&&yy>0&&yy<=m&&a[xx][yy]=='#') return 0; } return 1; } void change(int x,int y,int st[3][2],int s) { int i; for(i=0;i<3;i++) { int xx=x+st[i][0]; int yy=y+st[i][1]; if(xx<=0||xx>n) continue; if(yy<=0||yy>m) continue; vis[xx][yy]=s; } } void dfs(int d,int f,int temp) { if(temp>=ans) return ; if(d==num) { ans=temp; return ; } if(vis[x[d]][y[d]]) { dfs(d+1,f,temp); //这是这个位置被照亮不用灯的情况 } if(c[d]&&f!=d) //这个位置可以放灯，并且以前没有放过灯在这里 { change(x[d],y[d],step[0],1); dfs(d+1,f,temp+1); change(x[d],y[d],step[0],0); } } int main() { int i,j; while(~scanf("%d%d",&n,&m),n+m) { for(i=1;i<=n;i++) scanf("%s",a[i]+1); num=0; for(i=n;i;i--) for(j=1;j<=m;j++) if(a[i][j]=='.') { x[num]=i; y[num++]=j; } for(i=0;i