Submission #542070

#	Time	Username	Problem	Language	Result	Execution time	Memory
542070		AJ00	Tetris (COCI17_tetris)	C++14	80 / 80	1 ms	324 KiB

tetris

#include <bits/stdc++.h>
using namespace std;
#define int long long
//pair<int,int> rect[1000001]; 
char str[10][10];
bool visited[10][10];
int tile[5],adjsize;
vector<pair<int,int>> adj[11][11],cords;
set<int> x,y;
void dfs(int i, int j){
    visited[i][j] = true;
    x.insert(i);
    y.insert(j);
    adjsize = max(adjsize, (int)adj[i][j].size());
    cords.push_back({i,j});
    for (auto c: adj[i][j]){
        if (!visited[c.first][c.second]){
            dfs(c.first,c.second);
        }
    }
}
bool valid(int i, int j, int n, int m){
    return i >= 0 && i < n && j >= 0 && j < m;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1,n,m; 
    //cin >> t; 
    while (t--){
        cin >> n >> m;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                cin >> str[i][j];
            }
        }
       // cout << str[2][0]-'a' << " " << str[0][0]-'a' << "\n";
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (str[i][j]-'a' < 0){
                    continue;    
                }    
                if (valid(i+1,j,n,m) && str[i][j]-'a' == str[i+1][j]-'a'){
                    adj[i][j].push_back({i+1,j});
                    adj[i+1][j].push_back({i,j});
                }
                if (valid(i-1,j,n,m) && str[i][j]-'a' == str[i-1][j]-'a'){
                    adj[i][j].push_back({i-1,j});
                    adj[i-1][j].push_back({i,j});
                }
                if (valid(i,j+1,n,m) && str[i][j]-'a' == str[i][j+1]-'a'){
                    adj[i][j].push_back({i,j+1});
                    adj[i][j+1].push_back({i,j});
                }
                if (valid(i,j-1,n,m) && str[i][j]-'a' == str[i][j-1]-'a'){
                    adj[i][j].push_back({i,j-1});
                    adj[i][j-1].push_back({i,j});
                }
            }
        }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (!visited[i][j] && str[i][j]-'a' >= 0){
                    x.clear();
                    y.clear();
                   // cout << i+1 << " " << j+1 << " " << str[i][j] << " ";
                    adjsize = 0;
                    cords.clear();
                    dfs(i,j);
                    adjsize /= 2;
                    if (x.size() == 2 && y.size() == 2){
                        tile[0]++;
                        //cout << 1 << "\n";
                    } 
                    else if (x.size() == 1 || y.size() == 1){
                        tile[1]++;
                        //cout << 2 << "\n";
                    }
                    else if (adjsize == 3){
                        tile[4]++;
                        //cout << 5 << "\n";
                    }
                    else{
                        sort(cords.begin(),cords.end());
                        if (x.size() == 2){
                            if (cords[0].second == cords[3].second){
                                tile[2]++;
                             //   cout << 3 << "\n";
                            }
                            else {
                               // cout << 4 << "\n";
                                tile[3]++;
                            }
                        }
                        else {
                            if (cords[1].second + 1 == cords[0].second){
                                tile[3]++;
                               // cout << 4 << "\n";
                            }
                            else {
                                tile[2]++;
                               // cout << 3 << "\n";
                            }
                        }
                    }
                }
            }
        }
       // cout << adj[4][4].size() << " ";
        for (int i = 0; i < 5; i++){
            cout << tile[i] << "\n";
        }
    }
    return 0;
}

• Subtask 1: 80 / 80