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
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
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