这道题有几个陷阱:
1.灯光可以找到房间以外
2.只有一个可以旋转的灯
3.最多有十五个需要灯光的房间
4.一个房间最多只能有一盏灯
3 3
#.#
. . .
#.#
这组数据上错了好久。。。
大致解题思路:
记录下来需要灯光的发房间数,对其进行遍历,每一个进行四个方向的判断,安放可以旋转的灯。因为其余为L型灯,便可以从左下角进行搜索依次向右再向上,若是需要灯光的空房间,先判断是否可以放灯,如果不可以,再判断是否可以是L的右下部分,如果依然不可以,判断是否是L的左上部分(右下和左上情况注意,不能将灯安装在墙上),都行不通的话,该方法错误,如果全部遍历完成,则这种情况即为安放好旋转灯后最小的放置L灯的放法,进行判断记录最小值即可。
#include<iostream>
#include<cstring>
using namespace std;
int bank[210][210],l;
struct {int x;int y;
}v[20];
int main()
{int dir[4][2]={-1,0,0,1,1,0,0,-1};int n,m,num,p,q,min,u; while(cin>>n>>m&&n!=0&&m!=0){u=0;min=10000;num=0;getchar();int i,j;char ch;for(i=0;i<=n+1;i++){for(j=0;j<=m+1;j++){bank[i][j]=2;}}for(i=1;i<=n;i++){for(j=1;j<=m;j++){cin>>ch;if(ch=='#')bank[i][j]=0;if(ch=='.'){u=1;bank[i][j]=1;v[num].x=i;v[num].y=j;num++;}}getchar();}for(i=0;i<num;i++){for(j=0;j<4;j++){l=10000;if(bank[v[i].x+dir[j][0]][v[i].y+dir[j][1]]>0&&bank[v[i].x+dir[(j+1)%4][0]][v[i].y+dir[(j+1)%4][1]]>0){l=1;bank[v[i].x+dir[j][0]][v[i].y+dir[j][1]]++;bank[v[i].x+dir[(j+1)%4][0]][v[i].y+dir[(j+1)%4][1]]++;bank[v[i].x][v[i].y]=100;for(p=n;p>0;p--){for(q=1;q<=m;q++){if(bank[p][q]!=0){if(bank[p][q]==1){if(bank[p-1][q]>0&&bank[p][q+1]>0){bank[p-1][q]++;bank[p][q+1]++;bank[p][q]+=100;l++;}else if(bank[p][q-1]>0&&bank[p-1][q-1]>0&&bank[p][q-1]<100&&q-1>0){bank[p][q-1]+=100;bank[p-1][q-1]++;bank[p][q]++;l++;}else if(bank[p+1][q]>0&&bank[p+1][q+1]>0&&bank[p+1][q]<100&&p+1<=n){bank[p+1][q]+=100;bank[p+1][q+1]++;bank[p][q]++;l++;}else{l=-1;break;}}}}if(l==-1) break;}}if(l!=-1&&l<min) min=l;for(int t=0;t<num;t++){bank[v[t].x][v[t].y]=1;}}}if(u==0) cout<<0<<endl;else if(min==10000) cout<<-1<<endl;else cout<<min<<endl;}
}