Submission #2072649
Source Code Expand
//Multiple Pieces
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<time.h>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<set>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<random>
#include<cassert>
using namespace std;
#define LL long long
#define ROOP() while(true)
int p[50][50] = {};
bool pb[50][50];
int H,W,K;
vector<pair<int,int> > ans;
bool move(int nokori, int x, int y, int m){
if(nokori==0) return true;
if(y-1>=0 && p[x][y-1]>=m && pb[x][y-1]==false){
pb[x][y-1] = true;
ans.push_back(make_pair(y-1,x));
if(move(nokori-1, x, y-1, m)){
return true;
}
else{
pb[x][y-1] = false;
ans.pop_back();
}
}
if(y+1<50 && p[x][y+1]>=m && pb[x][y+1]==false){
pb[x][y+1] = true;
ans.push_back(make_pair(y+1,x));
if(move(nokori-1, x, y+1, m)){
return true;
}
else{
pb[x][y+1] = false;
ans.pop_back();
}
}
if(x-1>=0 && p[x-1][y]>=m && pb[x-1][y]==false){
pb[x-1][y] = true;
ans.push_back(make_pair(y,x-1));
if(move(nokori-1, x-1, y, m)){
return true;
}
else{
pb[x-1][y] = false;
ans.pop_back();
}
}
if(x+1<50 && p[x+1][y]>=m && pb[x+1][y]==false){
pb[x+1][y] = true;
ans.push_back(make_pair(y,x+1));
if(move(nokori-1, x+1, y, m)){
return true;
}
else{
pb[x+1][y] = false;
ans.pop_back();
}
}
return false;
}
void search(int m){
for(int i=0; i<H; i++){
for(int j=0; j<W; j++){
if(p[j][i]>=m && pb[j][i]==false){
pb[j][i] = true;
ans.push_back(make_pair(i,j));
if(!move(K-1, j, i, m)){
pb[j][i] = false;
ans.pop_back();
}
}
}
}
}
int main(){
cin >> H >> W >> K;
for(int i=0; i<H; i++){
string s;
cin >> s;
for(int j=0; j<W; j++){
p[j][i] = s[j] - '0';
pb[j][i] = false;
}
}
double MAX_TIME = 9.9;
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(9);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(8);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(7);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(6);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(5);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(4);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(3);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(2);
if(clock()/CLOCKS_PER_SEC < MAX_TIME) search(1);
ofstream outputfile("Desktop/C++/output.txt");
cout << ans.size()/8 << endl;
outputfile << ans.size()/8 << endl;
for(int i=0; i<ans.size(); i++){
cout << ans.at(i).first+1 << " " << ans.at(i).second+1 << endl;
outputfile << ans.at(i).first+1 << " " << ans.at(i).second+1 << endl;
}
outputfile.close();
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Multiple Pieces |
User |
Pro_ktmr |
Language |
C++14 (GCC 5.4.1) |
Score |
608362 |
Code Size |
2733 Byte |
Status |
AC |
Exec Time |
6 ms |
Memory |
512 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 |
62299 / 1343058 |
61127 / 1343058 |
58761 / 1343058 |
51667 / 1343058 |
68708 / 1343058 |
55206 / 1343058 |
66157 / 1343058 |
57999 / 1343058 |
64600 / 1343058 |
61838 / 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 |
512 KB |
subtask_01_02.txt |
AC |
5 ms |
256 KB |
subtask_01_03.txt |
AC |
5 ms |
256 KB |
subtask_01_04.txt |
AC |
5 ms |
256 KB |
subtask_01_05.txt |
AC |
5 ms |
256 KB |
subtask_01_06.txt |
AC |
5 ms |
256 KB |
subtask_01_07.txt |
AC |
5 ms |
256 KB |
subtask_01_08.txt |
AC |
5 ms |
256 KB |
subtask_01_09.txt |
AC |
5 ms |
256 KB |
subtask_01_10.txt |
AC |
5 ms |
256 KB |