Submission #18618682

Source Code Expand

Copy
```#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <array>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <cstring>
#include <unordered_map>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
if(x < y){
x = y;
return true;
}
return false;
}
template<class T>
inline bool chmin(T& x, T y){
if(x > y){
x = y;
return true;
}
return false;
}

constexpr int H = 50;
constexpr int W = 50;
constexpr int K = 8;
constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};
int grid[H][W];
bool used[H][W];
vector<P> ps;
vector<vector<P>> ans;

inline void input(){
int __;
cin >> __ >> __ >> __;
for(int r = 0; r < H; ++r){
for(int c = 0; c < W; ++c){
char ch;
cin >> ch;
grid[r][c] = ch - '0';
}
}
}

bool dfs(int r, int c){
ps.emplace_back(r, c);
used[r][c] = true;
if((int)ps.size() == K){
ans.emplace_back(ps);
ps.pop_back();
return true;
}
for(int i = 0; i < 4; ++i){
int nr = r + dx[i], nc = c + dy[i];
if(nr < 0 || nr >= H || nc < 0 || nc >= W)  continue;
if(used[nr][nc])    continue;
if(dfs(nr, nc)){
ps.pop_back();
return true;
}
}
ps.pop_back();
return used[r][c] = false;
}

void greedy(){
for(int r = 0; r < H; ++r){
for(int c = 0; c < W; ++c){
if(!used[r][c]) dfs(r, c);
}
}
}

inline void output(){
cout << ans.size() << '\n';
for(int i = 0; i < (int)ans.size(); ++i){
for(auto [r, c] : ans[i])   cout << r + 1 << ' ' << c + 1 << '\n';
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);

input();
greedy();
output();
}```

#### Submission Info

Submission Time 2020-12-06 23:29:19+0900 A - Multiple Pieces outline C++ (GCC 9.2.1) 57476 2393 Byte AC 9 ms 3664 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 5056 / 1343058 5984 / 1343058 7002 / 1343058 4788 / 1343058 3771 / 1343058 6558 / 1343058 6039 / 1343058 3923 / 1343058 6536 / 1343058 7819 / 1343058
Status
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
 AC × 1
Set Name Test Cases