fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(a) (a).begin(), (a).end()
  4. #define dbg_line(x) cout << (x) << '\n'
  5. #define dbg(x) cout << x << " "
  6.  
  7. using namespace std;
  8.  
  9. // <--> Report constants <-->
  10.  
  11. typedef pair<int, int> pii;
  12. const int max_n = 1e5 + 5;
  13. const ll inf = 1e9;
  14. const ll m_inf = -1e9;
  15. const ll mod = 1e9 + 7;
  16.  
  17. // <--> Report variables <-->
  18.  
  19. int n, m, k, t;
  20. char Nurikabe[1005][1005];
  21. int Number[1005][1005], parent[max_n], ranks[max_n];
  22. int dx[4] = {-1, 0, 0, 1};
  23. int dy[4] = {0, -1, 1, 0};
  24. int cnt = 0;
  25.  
  26. // <--> Main Code is Here <-->
  27.  
  28. void setIO(){
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(NULL);
  31.     cout.tie(NULL);
  32. }
  33.  
  34. void call_file(){
  35.     freopen("input.txt","r",stdin);
  36.     freopen("output.txt","w",stdout);
  37. }
  38.  
  39. int findSet(int u){
  40.     if (parent[u] == u) return u;
  41.     else return parent[u] = findSet(parent[u]);
  42. }
  43.  
  44. int toIndex(int i, int j){
  45.     return i * m + j;
  46. }
  47.  
  48. void unionSet(int u, int v){
  49.     int pu = findSet(u);
  50.     int pv = findSet(v);
  51.     if (pu == pv) return;
  52.     if (ranks[pu] > ranks[pv]){
  53.        parent[pv]  = pu; 
  54.     } else
  55.     if (ranks[pv] > ranks[pu]){
  56.         parent[pu] = pv;
  57.     }
  58.     else{
  59.         ranks[pu]++;
  60.         parent[pv] = pu;
  61.     }
  62. }
  63.  
  64. void dfs(int u, int v){
  65.     Nurikabe[u][v] = '@';
  66.     cnt++;
  67.     for (int i = 0; i < 4; i++){
  68.         int i1 = u + dx[i];
  69.         int j1 = v + dy[i];
  70.         if (i1 > 0 && i1 <= n && j1 > 0 && j1 <= m && Nurikabe[i1][j1] == '.'){
  71.             dfs(i1, j1);
  72.         }
  73.     }
  74. }
  75.  
  76. bool solve(){
  77.     for (int i = 1; i <= n; i++){
  78.         cnt = 0;
  79.         for (int j = 1; j <= m; j++){
  80.             if (Number[i][j] != 0){
  81.                 dfs(i, j);
  82.                 if (cnt != Number[i][j]){
  83.                     return false;
  84.                 }
  85.             }
  86.         }
  87.     }
  88.     for (int i = 1; i <= n; i++){
  89.         for (int j = 1; j <= m; j++){
  90.             if (Nurikabe[i][j] == '#' && Nurikabe[i + 1][j] == '#' && Nurikabe[i][j + 1] == '#' && Nurikabe[i + 1][j + 1] == '#'){
  91.                 return false;
  92.             }
  93.         }
  94.     }
  95.     int check = -1;
  96.     for (int i = 1; i <= n; i++){
  97.         for (int j = 1; j <= m; j++){
  98.             if (Nurikabe[i][j] == '#'){
  99.                 check = findSet(toIndex(i, j));
  100.                 break;
  101.             }
  102.         }
  103.         if (check != -1) break;
  104.     }
  105.     for (int i = 1; i <= n; i++){
  106.         for (int j = 1; j <= m; j++){
  107.             if (Nurikabe[i][j] == '#'){
  108.                 if (check != findSet(toIndex(i, j))){
  109.                     return false;
  110.                 }
  111.             }
  112.         }
  113.     }
  114.     return true;
  115.  
  116. }
  117.  
  118. void setup(){
  119.     for (int i = 1; i <= n * m; i++){
  120.         parent[i] = i;
  121.         ranks[i] = 1;
  122.     }
  123. }
  124.  
  125. int main(){
  126.     setIO();
  127.     call_file();
  128.     cin >> t;
  129.     for (int s = 1; s <= t; s++){
  130.         cout << "Puzzle #" << s << ":" << " ";
  131.         cin >> n >> m >> k;
  132.         setup();
  133.         for (int i = 1; i <= n; i++){
  134.             for (int j = 1; j <= m; j++){
  135.                 cin >> Nurikabe[i][j];
  136.             }
  137.         }
  138.         while(k--){
  139.             int r, c, v;
  140.             cin >> r >> c >> v;
  141.             Number[r][c] = v;
  142.         }
  143.         for (int i = 1; i <= n; i++){
  144.             for (int j = 1; j <= m; j++){
  145.                 if (Nurikabe[i][j] == '#'){
  146.                     if (j + 1 <= m && Nurikabe[i][j + 1] == '#'){
  147.                         unionSet(toIndex(i, j), toIndex(i, j + 1));
  148.                     }
  149.                     if (i + 1 <= n && Nurikabe[i + 1][j] == '#'){
  150.                         unionSet(toIndex(i, j), toIndex(i + 1, j));
  151.                     }
  152.                 }
  153.             }
  154.         }
  155.         if (solve()) cout << "Correct" << '\n';
  156.         else cout << "Incorrect" << '\n';
  157.     }
  158. }
  159.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gNW9db
language:
C++ (gcc 8.3)
created:
283 days 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!