CF 192 Div2

A.Cakeminator

暴搞之，從沒有草莓覆蓋的行、列遍歷

char map[30][30]; 
int vis[30][30]; 
int hang[30],lie[30]; 
int main() { 
 
    int n,m,i,j; 
    cin >> n >> m; 
    for(i=1; i<=n; i++) { 
        for(j=1; j<=m; j++) { 
            cin >> map[i][j]; 
            if(map[i][j] == 'S') { 
                hang[i] = 1; 
                lie[j] = 1; 
            } 
        } 
    } 
    for(i=1; i<=n; i++) { 
        if(hang[i] == 0) { 
            for(j=1; j<=m; j++) { 
                vis[i][j] = 1; 
            } 
        } 
    } 
    for(i=1; i<=m; i++) { 
        if(lie[i] == 0) { 
            for(j=1; j<=n; j++) { 
                vis[j][i] = 1; 
            } 
        } 
    } 
    int cnt = 0; 
    for(i=1; i<=n; i++) { 
        for(j=1; j<=m; j++) { 
            if(vis[i][j] == 1) 
                cnt++; 
        } 
    } 
    cout << cnt << endl; 
    return 0; 
} 

char map[30][30];
int vis[30][30];
int hang[30],lie[30];
int main() {

    int n,m,i,j;
    cin >> n >> m;
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            cin >> map[i][j];
            if(map[i][j] == 'S') {
                hang[i] = 1;
                lie[j] = 1;
            }
        }
    }
    for(i=1; i<=n; i++) {
        if(hang[i] == 0) {
            for(j=1; j<=m; j++) {
                vis[i][j] = 1;
            }
        }
    }
    for(i=1; i<=m; i++) {
        if(lie[i] == 0) {
            for(j=1; j<=n; j++) {
                vis[j][i] = 1;
            }
        }
    }
    int cnt = 0;
    for(i=1; i<=n; i++) {
        for(j=1; j<=m; j++) {
            if(vis[i][j] == 1)
                cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

B.Road Construction

從一個點到達其他點的距離小於等於2，那只有以一個點為中心，其它點只與它連接的建圖了

m < n/2 所有一定至少有一個點能做中心點

int vis[1005]; 
int main() { 
 
    int n,m,i,j,a,b; 
    cin >> n >> m; 
    for(i=1; i<=m; i++) { 
        cin >> a >> b; 
        vis[a] = 1; 
        vis[b] = 1; 
    } 
    int t; 
    for(i=1; i<=n; i++) { 
        if(vis[i] == 0){ 
          t = i; 
          break; 
        } 
    } 
    cout << n-1 << endl; 
    for(i=1; i<=n; i++) { 
        if(i != t) cout << i << ' ' << t << endl; 
    } 
    return 0; 
} 

int vis[1005];
int main() {

    int n,m,i,j,a,b;
    cin >> n >> m;
    for(i=1; i<=m; i++) {
        cin >> a >> b;
        vis[a] = 1;
        vis[b] = 1;
    }
    int t;
    for(i=1; i<=n; i++) {
        if(vis[i] == 0){
          t = i;
          break;
        }
    }
    cout << n-1 << endl;
    for(i=1; i<=n; i++) {
        if(i != t) cout << i << ' ' << t << endl;
    }
    return 0;
}

 

C.Purification

搞了很久，開始想太復雜了。尋找是否所有行或者所有列能被‘.’覆蓋，只要一條滿足，就可以直接輸出了

char map[105][105]; 
int x[105],y[105]; 
int main() { 
 
    int n,i,j; 
    cin >> n; 
    for(i=0; i<n; i++) { 
        cin >> map[i]; 
    } 
    for(i=0; i<n; i++) { 
        for(j=0; j<n; j++) { 
            if(map[i][j] == '.') { 
                x[i] = 1; 
                y[j] = 1; 
            } 
        } 
    } 
    int cntx = 0,cnty = 0; 
    for(i=0; i<n; i++) { 
        if(x[i] != 0) { 
            cntx++; 
        } 
        if(y[i] != 0) { 
            cnty++; 
        } 
    } 
    if(cnty <n && cntx <n) { 
        cout << -1 << endl; 
        return 0; 
    } 
    int flag = 0; 
    if(cntx == n) { 
        flag = 1; 
        for(i=0; i<n; i++) { 
            for(j=0; j<n; j++) { 
                if(map[i][j] == '.') { 
                    cout << i+1 << ' ' << j+1 << endl; 
                    break; 
                } 
            } 
        } 
    } 
    if(flag == 1) 
        return 0; 
    if(cnty == n) { 
        for(i=0; i<n; i++) { 
            for(j=0; j<n; j++) { 
                if(map[j][i] == '.') { 
                    cout << j+1 << ' ' << i+1 << endl; 
                    break; 
                } 
            } 
        } 
    } 
    return 0; 
} 

char map[105][105];
int x[105],y[105];
int main() {

    int n,i,j;
    cin >> n;
    for(i=0; i<n; i++) {
        cin >> map[i];
    }
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            if(map[i][j] == '.') {
                x[i] = 1;
                y[j] = 1;
            }
        }
    }
    int cntx = 0,cnty = 0;
    for(i=0; i<n; i++) {
        if(x[i] != 0) {
            cntx++;
        }
        if(y[i] != 0) {
            cnty++;
        }
    }
    if(cnty <n && cntx <n) {
        cout << -1 << endl;
        return 0;
    }
    int flag = 0;
    if(cntx == n) {
        flag = 1;
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                if(map[i][j] == '.') {
                    cout << i+1 << ' ' << j+1 << endl;
                    break;
                }
            }
        }
    }
    if(flag == 1)
        return 0;
    if(cnty == n) {
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                if(map[j][i] == '.') {
                    cout << j+1 << ' ' << i+1 << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

只過三道題，D,E沒看 。

賽後據說D是很水的bfs，所以沒寫。