# 29 条题解

• @ 2017-09-25 12:39:57
``````#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)

#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair

typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=1000+10;

int n;
bool gr[N][N],gc[N][N];
pi fr[N][N],fc[N][N];
int sr[N][N],sc[N][N];
int sumr[N][N],sumc[N][N];
int ans;
int qr(int x1,int y1,int x2,int y2) {
return sumr[x2][y2]+sumr[x1-1][y1-1]-sumr[x1-1][y2]-sumr[x2][y1-1];
}
int qc(int x1,int y1,int x2,int y2) {
return sumc[x2][y2]+sumc[x1-1][y1-1]-sumc[x1-1][y2]-sumc[x2][y1-1];
}
bool check(int x,int y) {
if (!gc[x][y]) return 0;
if (!gr[x][y]) return 0;
pi a=fr[x][y],b=fc[x][y];
int len1=b.fi-x+1,len2=a.se-y+1;
if (sc[x+len1-1][y]-sc[x-1][y]==len1&&
sr[x][y+len2-1]-sr[x][y-1]==len2&&
sc[x+len1-1][y+len2]-sc[x-1][y+len2]==len1&&
sr[x+len1][y+len2-1]-sr[x+len1][y-1]==len2) {
if (qc(x,y,x+len1-1,y+len2)+qr(x,y,x+len1,y+len2-1)==2*(len1+len2)) {
return 1;
}
}
return 0;
}
int main() {

std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

//freopen("in.txt","r",stdin);
cin>>n;
FOR(i,2*n) {
int cnt1=0,cnt2=0;
int flag=-1;
FOR(j,2*n) {
char t='\n';
while (t=='\n') cin.get(t);
if (i<=n) {
if ((flag==-1)&&(t=='/'||t=='\\')) {
flag=j%2;
}
if (flag==j%2) cnt1++;
if (flag!=-1&&flag!=j%2) cnt2++;
if (t=='/') {
gc[i-(cnt1-1)][1+(cnt1-1)]=1;
} else if (t=='\\') {
gr[i-(cnt2-1)][1+(cnt2-1)]=1;
}
} else {
if ((flag==-1)&&(t=='/'||t=='\\')) {
flag=j%2;
}
if (flag==j%2) cnt2++;// notice here is cnt2
if (flag!=-1&&flag!=j%2) cnt1++;
if (t=='/') {
gc[(n+1)-(cnt1-1)-1][i-n+(cnt1-1)+1]=1;
} else if (t=='\\') {
gr[(n+1)-(cnt2-1)][i-n+(cnt2-1)]=1;
}
}
}
}

/*
FOR(i,n) FOR(j,n+1) if (gc[i][j]) cout<<"("<<i<<","<<j<<")"<<" ";
cout<<endl;
FOR(i,n+1) FOR(j,n) if (gr[i][j]) cout<<"("<<i<<","<<j<<")"<<" ";
cout<<endl;
*/

FOR(j,n+1) for (int i=n;i>=1;i--) {
if (i<n) fc[i][j]=fc[i+1][j];
if (!gc[i][j]) fc[i][j]=mp(0,0);
else if (gr[i+1][j]||fc[i][j]==mp(0,0)) fc[i][j]=mp(i,j);
}
FOR(i,n+1) for (int j=n;j>=1;j--) {
if (j<n) fr[i][j]=fr[i][j+1];
if (!gr[i][j]) fr[i][j]=mp(0,0);
else if (gc[i][j+1]||fr[i][j]==mp(0,0)) fr[i][j]=mp(i,j);
}
FOR(i,n+1) FOR(j,n) sr[i][j]=sr[i][j-1]+(gr[i][j]>0);
FOR(j,n+1) FOR(i,n) sc[i][j]=sc[i-1][j]+(gc[i][j]>0);
FOR(i,n+1) FOR(j,n) sumr[i][j]=sumr[i-1][j]+sr[i][j];
FOR(j,n+1) FOR(i,n) sumc[i][j]=sumc[i][j-1]+sc[i][j];
FOR(i,n) FOR(j,n+1) if (check(i,j)) {
ans++;
}
cout<<ans<<endl;
return 0;
}
``````
• @ 2014-07-17 21:46:08

其实这道题不用转矩阵这么麻烦，矩阵的规律推起来不容易。
我用的是直接算的方法，虽然代码很长，但实际上条理性强，十分易懂。
每次搜索时寻找一个像/\一样的平行四边形的一角，分别往左右两边扩展，一旦有转向必须停止，向另一个方向扩展，直到再次遇到一个反向的。
扩展时记录每条边的长度，因为平行四边形两条对边相等，所以这里可以做一个判断。
然后再搜索平行四边形内的字符是否都为空格，这个可以做一个1-->len1+len2（平行四边形两条邻边之和）的循环，模拟同一行平行四边形的最左点和最右点，检查[left+1..right-1]区间内的字符即可。

测试数据 #0: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 3696 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 3692 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 3696 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 3692 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 3696 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 3692 KiB, score = 10
Accepted, time = 371 ms, mem = 3696 KiB, score = 100
虽然效率不是非常快，但结果还是很可观的。

以下为关键部分伪代码

这是扩展的伪代码
if pic[x+1,y]='\' then
trun_right
else
inc(x)
dec(y)

TRUN_RIGHT
if pic[x,y+1]='/' then
STOP
else
inc(x)
inc(y)

这是检查部分的伪代码
len1=length of first '/'
len2=length of first '\'
x=position of '/'
y=position of '\'
i:1-->len1+len2
{
go_left&down(x){i<len1}
go_right&down(y){i<len2}
go_right&down(x){i>=len1}
go_left&down(y){i>=len2}
j:x+1-->y-1
char=' '
}
注意，在扩展时，若遇到空格，即可判断为不合法。
在此Orz一下各位大神。

• @ 2009-11-06 16:14:14

发现tky的题都很不错啊

• @ 2009-06-27 18:10:17

floodfill……

ac 235！

• @ 2008-11-12 10:10:29

没转矩形果然累,不过蛮练代码能力的，最后cheat了一个数据。。。死活过不了

• @ 2008-11-10 19:07:42

前2次交都0分。。

• @ 2008-11-08 17:48:02

oibh上有

标程用的只是扫描……不是floodfill

• @ 2008-11-08 16:01:16

请问有没有标程可以提供

• @ 2008-11-07 20:33:32

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：97ms

数组开大啊！！！要1..2000,1..2000啊！

最后判断是不是矩形的时候只要把它连着的都填满，然后判断在这个被填满的里面有没有存在边

• @ 2008-11-07 19:40:17

ansistring...

longint...

白交兩次，而且每一次都是交給抽風狀態的DRAGON.

人品問題。

• @ 2008-10-31 08:50:18

for i:=1 to n do

for j:=2 to n do

if ch='/' then

begin

b:=true;b:=true;

end;

for i:=2 to n do

for j:=1 to n do

if ch='\' then

begin

b:=true;b:=true;

end;

这是我的转换公式~~~

• @ 2008-10-27 20:00:29

第一步：转矩形。。。虽然有不少大牛说不转矩形也可以做，但是我还是建议转矩形再做，因为转化不是很复杂，转成矩形做起来更直观。。。

第二步：染色。。。先把可以连通的所有方块染成一色，判断是否是矩形可以在后面做。。1遍DFS遍历搞定。。。顺便记录下每种颜色的方块数S和这种颜色的方块的MINX，MAXX，MINY，MAXY，X，Y指坐标，这个在后边判矩形有用。

第三步：判断是否构成矩形。。。先一步（MAXX-MINX+1）*（MAXY-MINY+1）=S粗略的判断是否构成矩形，可以证明不满足上式肯定不能构成矩形。

接着判断在该颜色的方块阵，有没有不该有的分界，

比如 _ _

| | |

|_ | 在这个方块阵中虽然都是同色,但他有不该有的分界,所有不能构成矩形....

三步的空间复杂度都是O(N^2)的,所以不会超时....这年头想一遍过的也只有这样的题了...-
-

• @ 2008-10-23 00:06:56

for i:=0 to n do

for j:=1 to n do

f[2*i+1,2*j]:=f[2*i+1,2*j-2]+ord(w[2*i+1,2*j]='-');

for i:=1 to n do

for j:=0 to n do

f[2*i,2*j+1]:=f[2*i,2*j-1]+ord(w[2*i,2*j+1]='|');

我的转换公式- -

就好象是模拟题一样..

• @ 2008-10-22 10:02:00

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：153ms

第一遍提交全超时，同样程序第二遍提交AC

卧槽泥马勒戈壁呀

• @ 2008-10-22 08:03:15

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 25ms

├ 测试数据 08：答案正确... 103ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 228ms

————————————————————

很慢，搜之前预处理一个点到左上和右上的‘/' '\'数目，然后搜起来用

• @ 2008-10-21 19:15:56

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

├ 错误行输出

├ 测试数据 10：答案错误...　├ 标准行输出

├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：20 有效耗时：0ms

为什么???

• @ 2008-10-21 13:01:12

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：200ms

• @ 2008-10-20 20:33:20

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 181ms

├ 测试数据 08：答案正确... 555ms

├ 测试数据 09：答案正确... 664ms

├ 测试数据 10：答案正确... 805ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2205ms

好险。。。

• @ 2008-10-20 13:48:32

对于一个有k个方块的连通块，它是矩形当且仅当

(max{x} - min{x}) * (max{y} - min{y}) = k

这样简便些

• @ 2008-10-20 12:41:16

用4位2进制数表示4个方向上是否有边

ID
1467

5

143

53

37%

2