第一行包含两个正整数 n, m ,表示地图的长和宽。
接下去 n 行,每行一个长为 m 的字符串,表示地图的一行。
其中 ‘.‘表示该位置未被打标记;‘#‘表示该位置被打了标记。保证地图仅由‘.‘和‘#‘构成。
输出仅一行,包含一个整数,表示你的答案。
4 4 .... .### .#.# .###
9
1 ≤ n x m ≤ 10^6.
解题思路:
AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int maxn=1e6+5; 5 int n,m,step;bool vis[maxn]; 6 vector<string> vec;string str; 7 int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; 8 void dfs(int a,int b){ 9 if(a<0||b<0||a>=n||b>=m||vis[a*m+b]||vec[a][b]==‘#‘)return; 10 vis[a*m+b]=true,step++,vec[a][b]=‘#‘; 11 for(int i=0;i<4;++i)dfs(a+dir[i][0],b+dir[i][1]); 12 } 13 int main(){ 14 while(cin>>n>>m){ 15 vec.clear(),step=0;memset(vis,false,sizeof(vis)); 16 for(int i=0;i<n;++i)cin>>str,vec.push_back(str); 17 for(int j=0;j<m;++j){ 18 if(vec[0][j]==‘.‘)dfs(0,j); 19 if(vec[n-1][j]==‘.‘)dfs(n-1,j); 20 } 21 for(int i=1;i<n-1;++i){ 22 if(vec[i][0]==‘.‘)dfs(i,0); 23 if(vec[i][m-1]==‘.‘)dfs(i,m-1); 24 } 25 cout<<n*m-step<<endl; 26 } 27 return 0; 28 }
本题有多组测试数据。
第一行一个正整数 T ,表示数据组数。
接下去 T 行,每行一个数 n ,表示寇族部落的个数。
输出共 T 行,每行一个字符串 "Ulamog, the Infinite Gyre" 或 "Kozilek, Butcher of Truth" 表示胜利者(去掉括号)。前者为无尽轮回钨拉莫,后者为真理屠夫寇基雷。
2 1 3
Kozilek, Butcher of Truth Ulamog, the Infinite Gyre
1 ≤ T ≤ 2000
1 ≤ n ≤ 2000
解题思路:
AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int T,n; 4 int main(){ 5 while(cin>>T){ 6 while(T--){ 7 cin>>n; 8 if(n==1)cout<<"Kozilek, Butcher of Truth"<<endl; 9 else cout<<"Ulamog, the Infinite Gyre"<<endl; 10 } 11 } 12 return 0; 13 }
原文:https://www.cnblogs.com/acgoto/p/9972613.html