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

  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 }

  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 }