codeforces 1-10 2014-03-28——2014-04-04

本文从WordPress迁移而来, 查看全部WordPress迁移文章

Codeforces Beta Round #33 (Codeforces format) B

http://codeforces.com/problemset/problem/33/B

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
/*
题意:给a,b串,给出一些字符转化的花费,将a,b变为一样,最小花费
不一定是a串变成b串或b串变为a串,可以两者都变成另一个新串
给出的那些字符变化,很容易抽象为图论模型,然后就是floyd了
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 100010

int map[30][30];
char a[MAX],b[MAX];
int lena,lenb,n;

int main(){
while(scanf("%s",a)!=EOF){
scanf("%s",b);
lena = strlen(a);
lenb = strlen(b);
memset(map,0x3f,sizeof(map));
scanf("%d",&n);
while(n--){
char s1[5],s2[5]; int w;
scanf("%s%s%d",s1,s2,&w);
map[s1[0]-'a'][s2[0]-'a'] = min(map[s1[0]-'a'][s2[0]-'a'],w);
}
for(int i = 0 ; i < 26; i++) map[i][i] = 0;
for(int k = 0; k < 26; k++){
for(int i = 0; i < 26; i++)
for(int j = 0; j < 26; j++)
map[i][j] = min(map[i][j] , map[i][k]+map[k][j]);
}
if(lena != lenb) { puts("-1"); continue; }
int ans = 0;
for(--lena; lena >= 0; lena--){
if(a[lena] == b[lena]) continue;
int Min = INF; char ch = '#';
for(int i = 0 ; i < 26; i++){
if(map[a[lena]-'a'][i]+map[b[lena]-'a'][i] < Min){
Min = map[a[lena]-'a'][i]+map[b[lena]-'a'][i];
ch = i+'a';
}
}
if(Min == INF) break;
ans += Min;
a[lena] = ch;
}
if(lena >= 0) { puts("-1"); continue; }
printf("%d\n",ans);
printf("%s\n",a);
}
return 0;
}
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
# -*- coding:utf-8 -*-
#ord()内置函数,将单个字符变为int
#chr()内置函数,将int变为单个字符
# for : else ( 或 while : else) 这个语法好用
INF = 1023423562


def main():
dp = [[INF]*30 for _ in range(30)]
a = raw_input()
b = raw_input()
n = int(raw_input())

for i in range(n):
s1,s2,w = raw_input().split()
w = int(w)
ida = ord(s1[0])-ord('a')
idb = ord(s2[0])-ord('a')
dp[ida][idb] = min(dp[ida][idb] , w)

for i in range(26):
dp[i][i] = 0
for k in range(26):
for i in range(26):
for j in range(26):
dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])

lena = len(a)
lenb = len(b)
if lena != lenb:
print '-1'
return

ans = 0
string = ""
for i in range(lena):
Min = INF
ch = '#'
ida = ord(a[i]) - ord('a')
idb = ord(b[i]) - ord('a')
for c in range(26):
if dp[ida][c] + dp[idb][c] < Min:
Min = dp[ida][c] + dp[idb][c]
ch = chr(ord('a')+c)
if Min == INF:
break
ans += Min
string = string+ch
else:
print ans
print string
return
print '-1'

main()

2. Codeforces Beta Round #63 (Div. 2) E

http://codeforces.com/problemset/problem/69/E

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
题意:给n个数字的序列,从最左端开始,取前k个数字,找出里面最大的数字,并且要求这个最大的数字在k个数字钟只出现一次,如果这个最大数出现了多次,输出nothing。然后,区间向右移动一格,还是k个数字,做同样的询问
用一个cnt数组记录每个数字出现了几次
求一个区间的最大值,用线城树实现
每次移动的时候,相当于删除一个数字,添加一个数字
另外,cnt从0变1,相当于在区间去插入一个数字,由1变多,或1变0,都相当于删除一个数字
反正用线段树维护还是很容易的
询问的话,其实每次都是询问整个区间的最大值(整个区间其实每个单元都只会有0,1的状态)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define LL long long
#define MAX 100010

int a[MAX];
int cnt[MAX];
int Hash[MAX],nh;
int n,m;
class SegTree{
public:
struct Node{
int l,r,mid,Max;
Node(){}
Node(int ll,int rr):l(ll),r(rr){ mid = (l+r)>>1; Max = 0; }
}t[MAX<<2];
int lson(int x) { return x<<1; }
int rson(int x) { return x<<1|1; }
void build(int rt,int a,int b){
t[rt] = Node(a,b);
if(a == b) return ;
int mid = t[rt].mid;
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}
void updata(int rt,int pos,int val){
if(t[rt].l == t[rt].r){
t[rt].Max = val;
return ;
}
int mid = t[rt].mid;
if(pos <= mid) updata(lson(rt),pos,val);
else updata(rson(rt),pos,val);
t[rt].Max = max(t[lson(rt)].Max,t[rson(rt)].Max);
}
int query(){ return t[1].Max; }
};

int find(int x){
int low = 1 , high = nh;
while(low <= high){
int mid = (low+high)>>1;
if(Hash[mid] == x) return mid;
else if(Hash[mid] < x) low = mid+1;
else high = mid-1;
}
}

void output(int id){
if(id == 0) puts("Nothing");
else printf("%d\n",Hash[id]);
}

int main(){
int id,res;
SegTree *T = new SegTree();
while(scanf("%d%d",&n,&m)!=EOF){
memset(cnt,0,sizeof(cnt));
for(int i = 1 ; i <= n; i++){
scanf("%d",&a[i]);
Hash[i] = a[i];
}
nh = 1;
sort(Hash+1,Hash+n+1);
for(int i = 2; i <= n; i++)
if(Hash[i] != Hash[i-1]) Hash[++nh] = Hash[i];
T->build(1,1,nh);
for(int i = 1; i <= m; i++){
id = find(a[i]);
if(cnt[id] == 0) { cnt[id]++; T->updata(1,id,id); }
else if(cnt[id] == 1) { cnt[id]++; T->updata(1,id,0); }
else cnt[id]++;
}

output(T->query());

for(int i = m+1; i <= n; i++){
id = find(a[i]);
if(cnt[id] == 0) { cnt[id]++; T->updata(1,id,id); }
else if(cnt[id] == 1) { cnt[id]++; T->updata(1,id,0); }
else cnt[id]++;
id = find(a[i-m]);
if(cnt[id] == 2) { cnt[id]--; T->updata(1,id,id); }
else if(cnt[id] == 1){ cnt[id]--; T->updata(1,id,0); }
else cnt[id]--;
output(T->query());
}
}
delete T;
return 0;
}

3. Codeforces Round #117 (Div. 2) D

http://codeforces.com/problemset/problem/182/D

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*
题意:给a,b串,找出他们各自有哪些循环节,然后看看它们有哪些公共的循环节
例如
a = abab
b = ababab
对于a来讲,ab,abab都是a串的循环节
对于b来讲,ab,abab,ababab都是b串的循环节
所以他们公共的循环节是ab,abab,输出2

做法是kmp,循环节,那就利用性质了
pre = len - next[len]
如果len % pre == 0,pre这个前缀就是最小循环节,若 len % pre != 0 , 这个串的循环节只有它自己
如果a,b串的最小循环节不同的话,他们是不会有公共循环节的,直接0
一个串除了最小循环节,还有什么循环节?
假设有4个最小循环节,那么1,2,4个最小循环节循环节都可以是串的循环节
加入有15个最小循环节,那么1,3,5,15个最小循环节都可以是串的循环节
嗯,就是,找,约数的个数!
如果a串有ca个最小循环节,找出ca的所有约数
如果b串有cb个最小循环节,找出cb的所有约数
有多少个公共的约数,就是答案
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define MAX 100010
#define LL long long

char a[MAX],b[MAX],sa[MAX],sb[MAX];
int nextT[MAX];
int ca[MAX],cb[MAX];

void getNext(char *T,int *next){
int i = 0 , j = -1 , lenT = strlen(T);
next[0] = -1;
while(i < lenT){
if(j == -1 || T[i] == T[j]) { ++i; ++j; next[i] = j; }
else j = next[j];
}
}

void getString(char *s,char *subs){
int lens = strlen(s),plen = lens - nextT[lens],sublens = 0;
if(lens % plen != 0) sublens = lens;
else sublens = plen;
for(int i = 0; i < sublens; i++)
subs[i] = s[i];
subs[sublens] = '\0';

}

void solve(int n,int *cnt){
//memset(cnt,0,sizeof(cnt));
int lim = (int)sqrt(n+0.5);
for(int p = 2; p <= lim && n > 1; p++){
if(n % p == 0){
while(n % p == 0){ cnt[p]++; n /= p; }
}
}
if(n > 1) cnt[n]++;
}

LL work(){
LL ans = 1LL;
for(int i = 2; i <= 100000; i++){
int t = min(ca[i],cb[i]);
ans *= (t+1);
}
return ans;
}

int main(){
int ra,rb;
while(scanf("%s",a)!=EOF){
scanf("%s",b);
int lena = strlen(a) , lenb = strlen(b);
getNext(a,nextT);
getString(a,sa);

getNext(b,nextT);
getString(b,sb);

if(strcmp(sa,sb)) { puts("0"); continue; }

int lensa = strlen(sa) , lensb = strlen(sb);
int cnta = lena / lensa , cntb = lenb / lensb;

//printf("%d --- %d\n",cnta,cntb);

memset(ca,0,sizeof(ca));
memset(cb,0,sizeof(cb));

solve(cnta,ca);
solve(cntb,cb);
cout << work() << endl;
}
return 0;
}

4. Codeforces Round #176 (Div. 2) C

http://codeforces.com/problemset/problem/287/C

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
/*
题意:略

位置 值
i p[i]
p[i] n-i+1
n-i+1 n-p[i]+1
n-p[i]+1 i

i p[i]
...............

可见是一个循环,循环节是4
如果n是4的倍数,那么可以够构造出来,如果模4余1也可以
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAX 100010

int a[MAX],n;

int main(){
while(scanf("%d",&n)!=EOF){
if(n % 4 > 1) puts("-1");
else{
int stpos = 1 , edpos = n-1;
int stval = 2 , edval = 1;
for(int i = 0; i < n/4; i++){
a[stpos] = stval;
a[edpos] = edval;
a[stpos+1] = n+2-stval;
a[edpos+1] = n-edval;
stpos += 2;
edpos -= 2;
stval += 2;
edval += 2;
}
if(n%4 == 1) a[stpos] = stval-1;
for(int i = 1; i <= n; i++)
printf("%d ",a[i]);
puts("");
}
}
return 0;
}
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
a = [0]*100010

n = int(raw_input())
if n % 4 > 1:
print '-1'
else:
stpos = 1
edpos = n-1
stval = 2
edval = 1
cnt = n/4
for i in range(cnt):
a[stpos] = stval
a[edpos] = edval
a[stpos+1] = n +2 - stval
a[edpos+1] = n - edval
stpos += 2
edpos -= 2
stval += 2
edval += 2
if n % 4 == 1:
a[stpos] = stval - 1
for i in range(1,n+1):
print a[i],
print '\n'

5. Codeforces Round #163 (Div. 2) C

http://codeforces.com/problemset/problem/266/C

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
题意:n*n的方阵,有n-1个1,其余都是0,可以交换两个列或两个行,使得所有1在主对角线下面
突破口是有n-1个1
那么肯定会有一行,是空行,即一个1都没有
把这行换到第1行,则可以保证第1行不会有1
判断第1列是不是为空,是的话,找一个非空的列和它交换
这样做,可以保证第1列的1处于合法位置,因为第1列的非法位置只有(1,1)
但是第1行是空的,所以(1,1)肯定不会有1
这时候可以去掉第1行,第1列(最外层)
以后交换只需要考虑第2行到第n行,第2列到第n列

重复迭代,直到整个矩阵合法为止,最多迭代n-1次
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
#define MAX 1111

struct op{
int k,i,j;
op(int kk,int ii,int jj):k(kk),i(ii),j(jj){}
void show(){ printf("%d %d %d\n",k,i,j); }
};
class matrix{
public:
int a[MAX][MAX];
int strow,stcol,n;
matrix(){}
matrix(int nn,int rr = 1,int cc = 1):n(nn),strow(rr),stcol(cc){}
void reset(int nn,int rr = 1,int cc = 1){
n = nn; strow = rr; stcol = cc;
memset(a,0,sizeof(a));
}
void swapRow(int i,int j){
for(int c = stcol; c <= n; c++) swap(a[i][c],a[j][c]);
}
void swapCol(int i,int j){
for(int r = strow; r <= n; r++) swap(a[r][i],a[r][j]);
}
bool judge(){
for(int r = strow; r <= n; r++)
for(int c = r; c <= n; c++)
if(a[r][c]) return false;
return true;
}
int findEmptyRow(){
int c;
for(int r = strow; r <= n; r++){
for(c = stcol; c <= n; c++)
if(a[r][c]) break;
if(c > n) return r;
}
}
int findNotEmptyCol(){
int r;
for(int c = stcol; c <= n; c++){
for(r = strow; r <= n; r++)
if(a[r][c]) return c;
}
}
void show(){
for(int r = strow; r <= n; r++){
for(int c = stcol; c <= n; c++)
printf("%d ",a[r][c]);
puts("");
}
}
};

matrix A;

int main(){
int n;
while(scanf("%d",&n)!=EOF){
A.reset(n,1,1);
for(int i = 1; i < n; i++){
int r,c;
scanf("%d%d",&r,&c);
A.a[r][c] = 1;
}
int ans = 0;
vector<op>save;
save.clear();
for(int i = 0; i < n; i++){
if(A.judge()) break;
int idr = A.findEmptyRow();
if(idr != A.strow){
save.push_back(op(1,A.strow,idr));
A.swapRow(A.strow,idr);
}
int idc = A.findNotEmptyCol();
if(idc != A.stcol){
save.push_back(op(2,A.stcol,idc));
A.swapCol(A.stcol,idc);
}
//A.show();
A.strow++;
A.stcol++;
}
printf("%d\n",save.size());
for(int i = 0; i < save.size(); i++)
save[i].show();
}
return 0;
}

6. Codeforces Round #173 (Div. 2) C

http://codeforces.com/problemset/problem/282/C

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
/*
题意:给两个01串,将a串变为b串。每次可以选择a串的两个数字做异或,或操作,得到的结果可以放回这两个位置
只要有1个1,就可以将整个串变为全1,然后再讲需要的位变为0,但最终最少都会留下1个1
所以只要只要判断一下特殊情况即可
如果b串全部是0,那么a串必须全0
如果b串有1,那么a串只要有1个1,就能变到b串1样,如果全0那没办法了
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAX 1000010

char a[MAX],b[MAX];
int cnta,cntb,lena,lenb;

int main(){
while(scanf("%s",a)!=EOF){
scanf("%s",b);
lena = strlen(a);
lenb = strlen(b);
if(lena != lenb) { puts("NO"); continue; }
cnta = cntb = 0;
for(int i = 0 ; i < lena; i++){
if(a[i] == '1') cnta++;
if(b[i] == '1') cntb++;
}
if(cntb == 0){
if(cnta == 0) puts("YES");
else puts("NO");
}
else{
if(cnta == 0) puts("NO");
else puts("YES");
}
}
return 0;
}

7. Codeforces Round #176 (Div. 2) D

http://codeforces.com/problemset/problem/287/D

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
/*
题意:一开始的序列是1,2,3....n,然后取k从2到n
对于一个k,就是在k个数字内,将第1个数字放到第k个数字后面,即组内轮换

不要在原来的空间上移动,把要移动的东西放到后面
n = 6
1 2 3 4 5 6
2 1 4 3 6 5
1 4 2 6 5 3
4 2 6 1 3 5
2 6 1 3 4 5
6 1 3 4 5 2
这样就可以 O(nlogn)去模拟了
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define N 1000010

int a[N*2],n,st,ed;

int main(){
while(scanf("%d",&n)!=EOF){
for(int i = 1; i <= n; i++)
a[i] = i;
for(int i = 2,head = 1; i <= n; i++,head++){
if(n % i){
st = head + n/i*i;
ed = head + n;
a[ed] = a[st];
}
st = head + (n/i-1)*i;
ed = st + i;
while(st >= head){
a[ed] = a[st];
st -= i;
ed -= i;
}
}
for(int i = n; i < 2*n; i++)
printf("%d ",a[i]);
puts("");
}
return 0;
}

8. Codeforces Beta Round #79 (Div. 2 Only) D

http://codeforces.com/problemset/problem/102/D

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/*
题意:有很多公交线路,你可以在车经过的途中上车(不能在终点上车),但是只能在终点下车,问去到终点的方案数
dp[r]表示走到r这个点有多少种方法
假设有一部车的路线是[l,r],即它是在r点下车的
那么只要在[l,r]内上了这辆车,都可以到达r
所以
dp[r] = dp[l] + dp[l+1] + dp[l+2] ..... + dp[r-1]

这是整个问题的dp方程
不过要解决几个问题
1.整个线段最多的点数是10^9,但车的数量只有10^5,很明显不是每个点都可以去到的,10^9很多是多余的
当然就是离散化了
2.每次都算 dp[l] + dp[l+1] + ....... + dp[r-1] 复杂度太高,很容易想到前缀和解决
sum[i] = dp[1] + dp[2] + dp[3] + ..... + dp[i]
3.对于一个点r,怎么知道有哪些车是在r点停的呢,不能暴力去找
其实我们是按照r从小到大去dp的,那么我们不妨把所有车的到达地方也排序,
这样每次找车都能接着上一次的
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAX 100010
#define LL long long
#define MOD 1000000007LL

int n,m,LEN,index;
int Hash[MAX<<1];
struct seg{
int l,r;
bool operator < (const seg &temp)const{
return r < temp.r;
}
}s[MAX];
LL dp[MAX<<1],sum[MAX<<1];

int find(int key){
int low = 0 , high = n-1;
while(low <= high){
int mid = (low + high) >> 1;
if(Hash[mid] == key) return mid;
else if(Hash[mid] < key) low = mid + 1;
else high = mid - 1;
}
}

int main(){
while(scanf("%d%d",&LEN,&m)!=EOF){
for(int i = 0; i < m; i++){
scanf("%d%d",&s[i].l,&s[i].r);
Hash[i<<1] = s[i].l; Hash[i<<1|1] = s[i].r;
}

n = 1;
sort(Hash,Hash+2*m);
for(int i = 1; i < 2*m; i++){
if(Hash[i] != Hash[i-1]) Hash[n++] = Hash[i];
}
if(Hash[n-1] != LEN || Hash[0] != 0) { puts("0"); continue; }

for(int i = 0; i < m; i++){
s[i].l = find(s[i].l);
s[i].r = find(s[i].r);
}
sort(s,s+m);

memset(dp,0,sizeof(dp));
memset(sum,0,sizeof(sum));
index = 0;
dp[0] = sum[0] = 1LL;
for(int i = 1; i < n; i++){
while(s[index].r < i && index < m) index++;
for(; index < m && s[index].r == i; index++){
dp[i] = (dp[i] + sum[i-1] - sum[s[index].l] + dp[s[index].l] + MOD) % MOD;
}
sum[i] = (sum[i-1] + dp[i]) % MOD;
}
cout << dp[n-1] << endl;
}
return 0;
}

9. Codeforces Round #122 (Div. 2) C

http://codeforces.com/problemset/problem/194/C

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
60
61
62
63
64
65
66
67
68
69
70
/*
题意:矩阵图,1是连通块,要删掉多少个1,可以让连通块断裂,性质证明是至多删除2个
后来想想,这个性质确实...........................
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAX 55

const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
char map[MAX][MAX];
int one,cr,cc,row,col;
bool vis[MAX][MAX];


bool judge(int r,int c){
if(r < 0 || r >= row || c < 0 || c >= col || map[r][c] != '#' || vis[r][c])
return false;
return true;
}

void dfs(int r,int c){
vis[r][c] = true;
for(int k = 0; k < 4; k++){
int rr = r + dx[k] , cc = c + dy[k];
if(judge(rr,cc)) dfs(rr,cc);
}
}

bool check(){
memset(vis,false,sizeof(vis));
vis[cr][cc] = true;
int count = 0;
for(int r = 0; r < row; r++)
for(int c = 0; c < col; c++)
if(map[r][c] == '#' && (r != cr || c != cc) && vis[r][c] == false){
count++;
dfs(r,c);
}
if(count > 1) return true;
else return false;
}

int solve(){
for(cr = 0; cr < row; cr++)
for(cc = 0; cc < col; cc++)
if(map[cr][cc] == '#'){
if(check()) return 1;
}
return 2;
}

int main(){
while(scanf("%d%d",&row,&col)!=EOF){
one = cr = cc = 0;
memset(map,0,sizeof(map));
for(int i = 0; i < row; i++){
scanf("%s",map[i]);
for(int j = 0; j < col; j++)
if(map[i][j] == '#') one++;
}
if(one <= 2) puts("-1");
else printf("%d\n",solve());
}
return 0;
}

10. Codeforces Round #173 (Div. 2) D

http://codeforces.com/problemset/problem/282/D

博弈,不会,稍后补