Submission #1191962
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
typedef long long ll;
typedef pair<int,int> p;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
int H, W, K;
string field[60];
int used[60][60];
struct node {
int y, x, spec;
bool operator<( const node& r ) const {
if (spec == r.spec && y == r.y) {
return x < r.x;
}
if (spec == r.spec) {
return y < r.y;
}
return spec < r.spec;
}
bool operator==( const node& r ) const {
return y == r.y && x == r.x;
}
bool operator!=( const node& r ) const {
return y != r.y || x != r.x;
}
};
map<node, node> par;
node last;
bool isOk(map<int,map<int,int> > &tmp_used, node n) {
// 範囲外
if (n.x < 0 || W <= n.x || n.y < 0 || H <= n.y) {
return false;
}
// 使用された or 数字がゼロ
if (tmp_used[n.y][n.x] || used[n.y][n.x] || field[n.y][n.x]=='0') {
return false;
}
return true;
}
int value(vector<node> &a) {
int ans = 1;
for (node x: a) {
ans *= x.spec;
}
return ans;
}
bool search(node n, int depth, map<int,map<int,int> > &tmp_used) {
if (depth==K) {
last = n;
return true;
}
priority_queue<node> q;
REP(i, 4) {
int ny = n.y + dy[i];
int nx = n.x + dx[i];
node nex = node{ny,nx,0};
if (isOk(tmp_used, nex)) {
nex.spec = field[ny][nx]-'0';
q.push(nex);
}
}
vector<vector<node> > ans;
while(!q.empty()) {
node nex = q.top();q.pop();
par[nex] = n;
map<int,map<int,int> > tu = tmp_used;
tu[nex.y][nex.x] = 1;
// cout << n.y << ", " << n.x << " to " << nex.y << ", " << nex.x << endl;
if (search(nex, depth+1, tu)){
if(depth >= 8) {return true;}
else {
node tpre = last;
vector<node> tans;
REP(i,K) {
tans.pb(tpre);
tpre = par[tpre];
}
ans.pb(tans);
}
}
}
int mans = 0;
for(vector<node> a:ans) {
int t = value(a);
if (mans < t) {
mans = t;
last = a[0];
REP(i, K-1) {
par[a[i]] = a[i+1];
}
}
}
if (mans) return true;
return false;
}
int main(){
ios::sync_with_stdio(false);
cin >> H >> W >> K;
priority_queue<node> q;
REP(i, H) {
cin >> field[i];
REP(j, W) q.push(node{(int)i,(int)j,field[i][j]-'0'});
}
vector< set<node> > lans;
while(!q.empty()) {
node a = q.top();q.pop();
if (used[a.y][a.x]) continue;
set<node> ans;
map<int,map<int,int> > tu;
tu[a.y][a.x] = 1;
if (search(a,1,tu)) {
REP(i,K) {
ans.insert(last);
used[last.y][last.x] = 1;
last = par[last];
}
lans.pb(ans);
}
}
cout << lans.size() << endl;
for (set<node> &sn: lans) {
for (node n: sn) {
cout << n.y+1 << " " << n.x+1 << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
yush1ga |
Language |
C++14 (GCC 5.4.1) |
Score |
557656 |
Code Size |
3589 Byte |
Status |
AC |
Exec Time |
211 ms |
Memory |
764 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 |
53084 / 1343058 |
51784 / 1343058 |
57394 / 1343058 |
53145 / 1343058 |
63401 / 1343058 |
50896 / 1343058 |
61880 / 1343058 |
54856 / 1343058 |
53936 / 1343058 |
57280 / 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 |
173 ms |
764 KB |
subtask_01_02.txt |
AC |
200 ms |
640 KB |
subtask_01_03.txt |
AC |
197 ms |
640 KB |
subtask_01_04.txt |
AC |
211 ms |
640 KB |
subtask_01_05.txt |
AC |
209 ms |
640 KB |
subtask_01_06.txt |
AC |
189 ms |
640 KB |
subtask_01_07.txt |
AC |
197 ms |
640 KB |
subtask_01_08.txt |
AC |
204 ms |
640 KB |
subtask_01_09.txt |
AC |
192 ms |
640 KB |
subtask_01_10.txt |
AC |
172 ms |
640 KB |