Submission #1400037

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int h = 50, w = 50, k = 8;
string s[51];
bool f[51][51];

vector<pair<int, int> > make_piece(int y, int x, int l){
    int dy[4] = {1, -1, 0, 0};
    int dx[4] = {0, 0, 1, -1};
    // bool g[51][51] = {};
    // for(int i = 0; i < h; i++){
    //     for(int j = 0; j < w; j++){
    //         g[i][j] = f[i][j];
    //     }
    // }
    vector<pair<int, int> > res;
    queue<pair<int, int> > q;
    q.push(pair<int, int>(y, x));
    res.push_back(pair<int, int>(y, x));
    f[y][x] = true;
    int cnt = 1;
    while(!q.empty()){
        pair<int, int> p = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];
            if(!(0 <= ny && ny < h && 0 <= nx && nx < w) || f[ny][nx]) continue;
            if((s[ny][nx] - '0') < l) continue;
            res.push_back(pair<int, int>(ny, nx));
            q.push(pair<int, int>(ny, nx));
            f[ny][nx] = true;
            cnt++;
            if(cnt == k) break;
        }
    }
    if(cnt == k) return res;
    for(int i = 0; i < res.size(); i++){
        f[res[i].first][res[i].second] = false;
    }
    res.clear();
    return res;
}

//sample : 13425万
int main(){
	cin >> h >> w >> k;
	for(int i = 0; i < h; i++) cin >> s[i];
	vector<vector<pair<int, int> > > ans;
    vector<pair<int, int> > tmp;
    
    for(int l = 7; l > 0; l--){
        for(int m = 9; m > 0; m--){
            for(int i = 0; i < h; i++){
                for(int j = 0; j < w; j++){
                    if((s[i][j] - '0') == m && f[i][j] == false){
                        tmp = make_piece(i, j, l);
                        // cout << tmp.size() << endl;
                        if(tmp.size() == k){
                            ans.push_back(tmp);
                        }
                    }
                }
            }
        }
    }

	int c = ans.size();
	cout << c << endl;
	for(int i = 0; i < c; i++){
		for(int j = 0; j < k; j++){
			cout << ans[i][j].first + 1 << " " << ans[i][j].second + 1 << endl;
		}
	}
}

Submission Info

Judge Result