Submission #1400817
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
struct UnionFind{
vector<int> par;
vector<int> sizes;
UnionFind(int n):par(n),sizes(n,1){
for(int i=0;i<n;i++)par[i] = i;
}
int find(int x){
if(x == par[x])return x;
return par[x] = find(par[x]);
}
void unite(int x,int y){
x = find(x);y = find(y);
if(x == y)return;
if(sizes[x] < sizes[y])swap(x,y);
par[y] = x;
sizes[x] += sizes[y];
}
bool same(int x,int y){
return find(x) == find(y);
}
int size(int x){
return sizes[find(x)];
}
};
int dx[] = {0,1,0,-1};
int dy[] = {-1,0,1,0};
class Search{
public:
int used[51][51];
int maxpoint;
vector<int> vx,vy;
vector<int> bestvx,bestvy;
vector<string> s;
Search(vector<string> s){
maxpoint = -1;
this->s = s;
}
void init(){
maxpoint = -1;
vx = vector<int>();
vy = vector<int>();
bestvx = vector<int>();
bestvy = vector<int>();
}
void dfs(int y,int x,int d,int point){
if(d == 8) {
if(point > maxpoint){
maxpoint = point;
bestvx = vx;
bestvy = vy;
}
return;
}
for(int i=0;i<4;i++){
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= 50 || ny >= 50)continue;
if(used[ny][nx] != 0)continue;
if(s[ny][nx] == '0')continue;
used[y][x] = 1;
vx.push_back(x);vy.push_back(y);
dfs(ny,nx,d+1,point * (s[y][x] - '0'));
vx.pop_back();vy.pop_back();
used[y][x] = 0;
}
}
void run(){
memset(used,0,sizeof(used));
int col = 1;
vector<vector<int>> vvx,vvy;
for(int y=0;y<50;y++){
for(int x=0;x<50;x++){
init();
if(used[y][x] != 0)continue;
dfs(y,x,0,1);
if(bestvx.size() == 0)continue;
for(int i=0;i<8;i++){
used[bestvy[i]][bestvx[i]] = col;
}
vvx.push_back(bestvx);
vvy.push_back(bestvy);
col++;
}
}
cout << vvx.size() << endl;
for(int i=0;i<vvx.size();i++){
for(int j=0;j<8;j++){
cout << vvy[i][j]+1 << " " << vvx[i][j]+1 << endl;
}
}
}
};
int main(void){
int H,W,K;
cin >> H >> W >> K;
vector<string> s(H);
for(int i=0;i<H;i++){
cin >> s[i];
}
Search search(s);
search.run();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
tkzw_21 |
Language |
C++14 (GCC 5.4.1) |
Score |
149829 |
Code Size |
2390 Byte |
Status |
AC |
Exec Time |
7 ms |
Memory |
256 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
14794 / 1343058 |
14882 / 1343058 |
13503 / 1343058 |
13022 / 1343058 |
15428 / 1343058 |
15099 / 1343058 |
17182 / 1343058 |
13504 / 1343058 |
17048 / 1343058 |
15367 / 1343058 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
6 ms |
256 KB |
subtask_01_02.txt |
AC |
6 ms |
256 KB |
subtask_01_03.txt |
AC |
6 ms |
256 KB |
subtask_01_04.txt |
AC |
7 ms |
256 KB |
subtask_01_05.txt |
AC |
7 ms |
256 KB |
subtask_01_06.txt |
AC |
6 ms |
256 KB |
subtask_01_07.txt |
AC |
6 ms |
256 KB |
subtask_01_08.txt |
AC |
6 ms |
256 KB |
subtask_01_09.txt |
AC |
7 ms |
256 KB |
subtask_01_10.txt |
AC |
6 ms |
256 KB |