杭电4770

news/2024/10/22 16:31:42/

这道题有几个陷阱:

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;}
} 




http://www.ppmy.cn/news/147414.html

相关文章

Core i7-4770K的详细性能

新品发布前总能看到一些规格、性能方面的偷跑&#xff0c;但大多都是零零碎碎的&#xff0c;关键时刻还得看权威大站。Toms Hardware今天放出猛料&#xff0c;公布了Intel Haswell处理器家族旗舰型号Core i7-4770K的详细性能&#xff0c;基本可以对下代平台有个整体的印像了。 …

P4770 [NOI2018]你的名字

蒟蒻表示不会sam凉凉了&#xff0c;所以只能提高SA技巧&#xff1f; 题意&#xff1a;有一个串\(A\)&#xff0c;每次选择一个\(A\)的子串\(A\)&#xff0c;以及串\(B\)&#xff0c;问\(B\)的所有本质不同子串中不在\(A\)中的串的数量。 &#xff08;定义\(A_i\)表示以字符\(A_…

hdu4770 状态压缩+枚举

http://acm.hdu.edu.cn/showproblem.php?pid4770 Problem Description Harry: "But Hagrid. How am I going to pay for all of this? I havent any money." Hagrid: "Well theres your money, Harry! Gringotts, the wizard bank! Aint no safer place. Not…

BZOJ4770: 图样 (随机点值求异或最小生成树边权和)

题目描述&#xff1a; n ≤ 50 , m ≤ 8 n\le50,m\le8 n≤50,m≤8 题目分析&#xff1a; 根据最小生成树有小到大加入边可以将点按照二进制最高位分组&#xff0c;统计所有情况的边权和。 Code&#xff1a; #include<bits/stdc.h> #define maxn 55 #define maxm 9 u…

【JZOJ4770】闭门造车

Description 自从htn体验了一把飙车的快感&#xff0c;他就下定决心要闭门造车&#xff01;但是他两手空空怎么造得出车来呢?无奈的他只好来到了汽车零部件商店。 一走进商店&#xff0c;玲琅满目的各式零件看得htn眼花缭乱。但是他很快便反应过来:我只要买一套好的零件就行…

chmod 4770的第一位解释

权限标志通过三个“位”来定义&#xff0c;分别是&#xff1a; setuid&#xff1a;设置使文件在执行阶段具有文件所有者的权限。比如/usr/bin/passwd&#xff0c;如果一般用户执行该文件&#xff0c;则在执行过程中&#xff0c;该文件可以获得root权限&#xff0c;从而可以更改…

Jzoj4770 闭门造车

自从htn体验了一把飙车的快感&#xff0c;他就下定决心要闭门造车&#xff01;但是他两手空空怎么造得出车来呢?无奈的他只好来到了汽车零部件商店。 一走进商店&#xff0c;玲琅满目的各式零件看得htn眼花缭乱。但是他很快便反应过来:我只要买一套好的零件就行。首先它们的性…

BZOJ 4770: 图样(恶心概率期望DP)

题目 考试时推到 p p p就嫌麻烦&#xff0c;不想推了。。。 讲真写好DP预处理调一年。 时间复杂度 O ( n 4 m 2 m ) O(n^4m2^m) O(n4m2m)的代码 T E ( b u t c o r r e t ) C o d e \mathrm {TE (but \ corret)\ Code} TE(but corret) Code //#pragma GCC optimize(3) #inc…