牛客练习赛31A（简单搜索找闭环，存图字符方式(二维转一维)，string和char技巧）

题目链接：https://ac.nowcoder.com/acm/contest/218/A

关键2点：

1.从边界处找闭环（这个很好想到）

2.存图(字符)方式不爆，二维转一维计算

（另外string s[maxn]，直接字符串数组也可以！当初被误导了没想起来唉QAQ~~）

关于第2点，深受痛感（string这么慢的吗我的天QAQ），再次发现了string使比char慢这么多！（好像是第二次了，经过这次想起了以前好像也遇见过一次！同样的代码string一直超时换成char就过！）（然后另外vector又比string s[maxn]好像还要慢!）

还有，string s

不能s[0]='1',s[1]='1'这样直接访问下标使用！（只能s=s+'1'这样加法使用）

char s; 可以s[0]='1'.s[1]='1'使用！

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <queue>
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <cmath>
  9 using namespace std;
 10 typedef long long ll;
 11 const int maxn=1e6+1;
 12 char s[maxn];
 13 ll n,m,cnt;
 14 struct px
 15 {
 16     ll x;
 17     ll y;
 18 }T;
 19 queue<px> que;
 20  
 21 ll trans(ll x,ll y)
 22 {
 23     return x*m+y;
 24 }
 25  
 26 void so(ll x,ll y)
 27 {
 28     T.x=x;
 29     T.y=y;
 30     que.push(T);
 31  
 32     ll t=0;
 33     while(que.size())
 34     {
 35         px p=que.front(); que.pop();
 36  
 37         //右
 38         if(p.y+1<=m-1)
 39         {
 40             t=trans(p.x,p.y+1);
 41             if(s[t]=='.')
 42             {
 43                 cnt++;
 44                 s[t]='#';
 45                 T.x=p.x;
 46                 T.y=p.y+1;
 47                 que.push(T);
 48             }
 49         }
 50         //下
 51         if(p.x+1<=n-1)
 52         {
 53             t=trans(p.x+1,p.y);
 54             if(s[t]=='.')
 55             {
 56                 cnt++;
 57                 s[t]='#';
 58                 T.x=p.x+1;
 59                 T.y=p.y;
 60                 que.push(T);
 61             }
 62         }
 63         //上
 64         if(p.x-1>=0)
 65         {
 66             t=trans(p.x-1,p.y);
 67             if(s[t]=='.')
 68             {
 69                 cnt++;
 70                 s[t]='#';
 71                 T.x=p.x-1;
 72                 T.y=p.y;
 73                 que.push(T);
 74             }
 75         }
 76         //左
 77         if(p.y-1>=0)
 78         {
 79             t=trans(p.x,p.y-1);
 80             if(s[t]=='.')
 81             {
 82                 cnt++;
 83                 s[t]='#';
 84                 T.x=p.x;
 85                 T.y=p.y-1;
 86                 que.push(T);
 87             }
 88         }
 89     }
 90 }
 91  
 92 int main()
 93 {
 94     ios::sync_with_stdio(false); cin.tie(0);
 95  
 96  
 97     cin>>n>>m;
 98     int p=0;
 99     for(int i=0;i<=n-1;i++)
100     {
101         for(int j=0;j<=m-1;j++)
102         {
103             cin>>s[p++];
104         }
105     }
106  
107     ll s1=0,s2=0,t1=0;
108     for(int j=0;j<=m-1;j++)
109     {
110         s1=0,s2=j;
111         t1=trans(s1,s2);
112         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
113  
114         s1=n-1,s2=j;
115         t1=trans(s1,s2);
116         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
117     }
118     for(int i=0;i<=n-1;i++)
119     {
120         s1=i,s2=0;
121         t1=trans(s1,s2);
122         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
123  
124         s1=i,s2=m-1;
125         t1=trans(s1,s2);
126         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
127     }
128  
129     ll temp=n*m;
130     ll ans=temp-cnt;
131     cout<<ans<<endl;
132  
133     return 0;
134 }

接下来，一模一样的代码，只是把char换成string就超时！

  1 #include <iostream>
  2 #include <string>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <queue>
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <cmath>
  9 using namespace std;
 10 typedef long long ll;
 11 const int maxn=1e6+1;
 12 string s;
 13 ll n,m,cnt;
 14 struct px
 15 {
 16     ll x;
 17     ll y;
 18 }T;
 19 queue<px> que;
 20 
 21 ll trans(ll x,ll y)
 22 {
 23     return x*m+y;
 24 }
 25 
 26 void so(ll x,ll y)
 27 {
 28     T.x=x;
 29     T.y=y;
 30     que.push(T);
 31 
 32     ll t=0;
 33     while(que.size())
 34     {
 35         px p=que.front(); que.pop();
 36 
 37         //右
 38         if(p.y+1<=m-1)
 39         {
 40             t=trans(x,y+1);
 41             if(s[t]=='.')
 42             {
 43                 cnt++;
 44                 s[t]='#';
 45                 T.x=p.x;
 46                 T.y=p.y+1;
 47                 que.push(T);
 48             }
 49         }
 50         //下
 51         if(p.x+1<=n-1)
 52         {
 53             t=trans(x+1,y);
 54             if(s[t]=='.')
 55             {
 56                 cnt++;
 57                 s[t]='#';
 58                 T.x=p.x+1;
 59                 T.y=p.y;
 60                 que.push(T);
 61             }
 62         }
 63         //上
 64         if(p.x-1>=0)
 65         {
 66             t=trans(x-1,y);
 67             if(s[t]=='.')
 68             {
 69                 cnt++;
 70                 s[t]='#';
 71                 T.x=p.x-1;
 72                 T.y=p.y;
 73                 que.push(T);
 74             }
 75         }
 76         //左
 77         if(p.y-1>=0)
 78         {
 79             t=trans(x,y-1);
 80             if(s[t]=='.')
 81             {
 82                 cnt++;
 83                 s[t]='#';
 84                 T.x=p.x;
 85                 T.y=p.y-1;
 86                 que.push(T);
 87             }
 88         }
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     ios::sync_with_stdio(false); cin.tie(0);
 95 
 96 
 97     cin>>n>>m;
 98     int p=0;
 99     for(int i=0;i<=n-1;i++)
100     {
101         for(int j=0;j<=m-1;j++)
102         {
103             char c;
104             cin>>c;
105 
106             s=s+c;
107         }
108     }
109 
110     ll s1=0,s2=0,t1=0;
111     for(int j=0;j<=m-1;j++)
112     {
113         s1=0,s2=j;
114         t1=trans(s1,s2);
115         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
116 
117         s1=n-1,s2=j;
118         t1=trans(s1,s2);
119         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
120     }
121     for(int i=0;i<=n-1;i++)
122     {
123         s1=i,s2=0;
124         t1=trans(s1,s2);
125         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
126 
127         s1=i,s2=m-1;
128         t1=trans(s1,s2);
129         if(s[t1]=='.') { s[t1]='#'; cnt++; so(s1,s2); }
130     }
131 
132     ll temp=n*m;
133     ll ans=temp-cnt;
134     cout<<ans<<endl;
135 
136     return 0;
137 }

string+dfs简洁版（这个才是我最初想要的想法）

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <cmath>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn=1e6+5;
10 string maze[maxn];
11 ll n,m,cnt;
12 
13 void so(int x,int y)
14 {
15     //右
16     if(y+1<=m-1 && maze[x][y+1]=='.') { maze[x][y+1]='#'; cnt++; so(x,y+1); }
17     //下
18     if(x+1<=n-1 && maze[x+1][y]=='.') { maze[x+1][y]='#'; cnt++; so(x+1,y); }
19     //上
20     if(x-1>=0 && maze[x-1][y]=='.') { maze[x-1][y]='#'; cnt++; so(x-1,y); }
21     //左
22     if(y-1>=0 && maze[x][y-1]=='.') { maze[x][y-1]='#'; cnt++; so(x,y-1); }
23 }
24 
25 int main()
26 {
27     ios::sync_with_stdio(false); cin.tie(0);
28 
29     cin>>n>>m;
30     for(int i=0;i<=n-1;i++) cin>>maze[i];
31 
32     //每行第一列和最后一列
33     for(int i=0;i<=n-1;i++)
34     {
35         if(maze[i][0]=='.') { maze[i][0]='#'; cnt++; so(i,0); }
36         if(maze[i][m-1]=='.') { maze[i][m-1]='#'; cnt++; so(i,m-1); }
37     }
38     //每列第一行和最后一行
39     for(int j=0;j<=m-1;j++)
40     {
41         if(maze[0][j]=='.') { maze[0][j]='#'; cnt++; so(0,j); }
42         if(maze[n-1][j]=='.') { maze[n-1][j]='#'; cnt++; so(n-1,j); }
43     }
44 
45     ll ans=n*m-cnt;
46     cout<<ans<<endl;
47 
48     return 0;
49 }

完。