fork download
copy 
  1. // i wants to take ioi
  2. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define int long long
  8. #define nn "\n"
  9. #define pi pair<int, int>
  10. #define fi first
  11. #define se second
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define eb emplace_back
  15. #define pb push_back
  16. #define TASK " "
  17.  
  18. #define ms(a, x) memset(a, x, sizeof(a))
  19. #define all(a) a.begin(), a.end()
  20. #define All(a, n) a + 1, a + 1 + n
  21.  
  22. #define LOG 19
  23.  
  24.  
  25. const int INF = 1e18;
  26. const int mod = 1e9;
  27. const int N = 20  + 5;
  28. int MOD = 998244353;
  29. int bit[200000];
  30. struct node{
  31. 	int kc, u, hk;
  32. 	bool operator<(const node& other) const {
  33.         return kc > other.kc;
  34.     }
  35. };
  36. struct edge{
  37. 	int v, w, h;
  38. };
  39.  
  40. void nhap(){
  41.  
  42. }
  43. char a[N][N];
  44. bool vis[N][N];
  45. int dx[] = {0, 0, -1, 1};
  46. int dy[] = {1, -1, 0, 0};
  47. int m, n;
  48. bool bfs(int sx, int sy){
  49.     queue<pi> q;
  50.     q.push({sx, sy});
  51.     vis[sx][sy] = 1;
  52.     while(!q.empty()){
  53.         int u = q.front().fi, v = q.front().se;
  54.         q.pop();
  55.         if((u == 1 || u == m || v == 1 || v == n) && a[u][v] == '.' && (u != sx || v != sy)){
  56.             return 1;
  57.         }
  58.         for(int i = 0; i < 4; i++){
  59.             int x = u + dx[i];
  60.             int y = v + dy[i];
  61.             if(x < 1 || y < 1 || x > m || y > n || a[x][y] == '#') continue;
  62.             if(!vis[x][y]){
  63.                 vis[x][y] = 1;
  64.                 q.push({x, y});
  65.             }
  66.         }
  67.     }
  68.     return 0;
  69. }
  70. void solve(){
  71.     cin >> m >> n;
  72.     for(int i = 1; i <= m; i++){
  73.         for(int j= 1; j <= n; j++){
  74.             cin >> a[i][j];
  75.             vis[i][j] = 0;
  76.         }
  77.     }
  78.     bool ok = 0;
  79.     vector<pi> v;
  80.  
  81.     for(int i = 1; i <= m; i++){
  82.         if(a[i][1] == '.'){
  83.             v.eb(i, 1);
  84.         }
  85.         if(a[i][n] == '.'){
  86.             v.eb(i, n);
  87.         }
  88.     }
  89.     for(int i = 1; i <= n; i++){
  90.         if(a[1][i] == '.'){
  91.             v.eb(1, i);
  92.         }
  93.         if(a[m][i] == '.'){
  94.             v.eb(m, i);
  95.         }
  96.     }
  97.     sort(v.begin(), v.end());
  98.     v.erase(unique(v.begin(), v.end()), v.end());
  99.     if(v.size() == 2){
  100.         if(bfs(v[0].fi, v[0].se)){
  101.             cout << "valid" << nn;
  102.         }
  103.         else cout << "invalid" << nn;
  104.     }
  105.     else cout << "invalid" << nn;
  106.  
  107. }
  108. signed main() {
  109. //	 freopen("m_mu_n.inp", "r", stdin);
  110. //	 freopen("m_mu_n.out", "w", stdout);
  111. 	ios_base::sync_with_stdio(0);
  112. 	cin.tie(0);
  113. 	cout.tie(0);
  114. 	int t; cin >> t;
  115.     while(t--) solve();
  116. 	return (0 ^ 0);
  117.  
  118. }
  119.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6
4 4
####
#...
#.##
#.##
5 5
#.###
#..##
##..#
#.#.#
###.#
1 1
.
5 1
#
#
.
.
#
2 2
#.
.#
3 4
#..#
#.##
#.##
stdout
copy 
valid
valid
invalid
valid
invalid
invalid
https://ideone.com/p0wYEm
language:
C++14 (gcc 8.3)
created:
13 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!