数据点望 Luogu 能完善下
好，讲解正式开始。
拿到正确题目后，能想到的就是模拟、暴力。虽然这是一道普及的题目，我们也要将代码优化得更加 短小精干。
我们要模拟啥呢？
1、首先，对于每一个牛，我们都要检查他能不能离开。
对于每一个牛，它上方格子或右方格子中，一定要有一条完全没有其他牛。
就说上文的样例。 号上方有 号，向上走行不通。同时有房还有 号，向右走，也行不通。所以这头牛就不能安全逃出。
同样我们可以看出，要让整个图安全，只要去掉 ，， 的任意一个，就可以解决纠纷了。
2、其次，如果不是安全的图，我们要尝试去掉每一个牛，来尝试能否使图变得安全。
这里，我似乎想到一个优化的方法，就是将发生冲突的牛记录下来，在去牛的时候只检查这些就够了。
可惜数据太小，也没太大用，这里只起抛砖引玉的效果。
用上面这两条足以通过此题。
上代码！
时间复杂度：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<bits/stdc++.h>
using namespace std;
int mp[51][51];
int cowx[101],
cowy[101];
int r,c,n,x,y;
char t[201];
bool check(int x,int y)
{
bool flag1=1,flag2=1;
for(int i=x-1;i>=1;i--) if(mp[i][y]) {flag1=false;break;}
for(int i=y+1;i<=c;i++) if(mp[x][i]) {flag2=false;break;}
return flag1||flag2;
}
bool checkALL()
{
bool ok=true;
for(int i=1;i<=n;i++)
{
int x=cowx[i],y=cowy[i];
if(mp[x][y]&&check(x,y)==false)
{
ok=false;
break;
}
}
return ok;
}
int main()
{
cin>>r>>c>>n;
for(int i=1;i<=n;i++)
{
cin>>cowx[i]>>cowy[i];gets(t);
mp[cowx[i]][cowy[i]]=i;
}
if(checkALL()) cout<<0;
else
{
for(int i=1;i<=n;i++)
{
mp[cowx[i]][cowy[i]]=0;
if(checkALL())
{
if(!mp[0][0]) mp[0][0]=true;
cout<<i<<endl;
}
mp[cowx[i]][cowy[i]]=i;
}
if(!mp[0][0]) cout<<-1;
}
return 0;
}
|
有啥问题？留言问我。
jr 的第二篇题解 awa
cnt = 2