Submission #2078665

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};

int H, W, K;
vector<string> grid;
int board[50][50];
bool visit[50][50];

void disp_board(void){
	rep (i, H){
		rep (j, W){
			cerr << board[i][j];
		} // end rep
		cerr << endl;
	} // end rep
}

vector<int> solve(int cr, int cc){
	vector<int> res; res.clear();
	queue<int> que;
	que.push(cr * W + cc);
	while(!que.empty() && (int)res.size() < K){
		int curr = que.front(); que.pop();
		cr = curr / W;
		cc = curr % W;
		if (!visit[cr][cc]){
			visit[cr][cc] |= true;
			res.push_back(cr * W + cc);
		} // end if
		for (int k = 0; k < 4; ++k){
			int nr = curr / W + dr[k];
			int nc = curr % W + dc[k];
			if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
			if (!visit[nr][nc]){
				que.push(nr * W + nc);
			} // end if
		} // end for
	} // end while
	return ((int)res.size() == K ? res : vector<int>());
}			

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(board, 0, sizeof(board));
	memset(visit, false, sizeof(visit));
	grid.clear();
	cin >> H >> W >> K;
	grid.resize(H, string(W, '0'));
	rep (i, H){
		cin >> grid[i];
	} // end rep
	rep (i, H) rep (j, W) board[i][j] = (int)(grid[i][j] - '0');
	rep (i, H) rep (j, W) visit[i][j] = (bool)(board[i][j] == 0);

//	disp_board();
	vector<vector<int> > res; res.clear();
	rep (i, H) rep (j, W){
		if (!visit[i][j]){
			vector<int> ans = solve(i,j);
			if (!ans.empty()){
				res.push_back(ans);
			} // end if
		} // end if
	} // end rep
	cout << (int)res.size() << endl;
	rep (i, (int)res.size()){
		rep (j, (int)res[i].size()){
			int x = res[i][j] % W;
			int y = res[i][j] / W;
			cout << y + 1 << ' ' << x + 1 << endl;
		} // end rep
	} // end rep
	
	return 0;
}

Submission Info

Judge Result