Submission #1142049

---

Source Code Expand

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <list>
#include <utility>
#include <set>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <random>

using namespace std;

static const double EPS = 1e-9;
template<class T> bool INRANGE(T x, T a, T b) { return a <= x&&x <= b; }
template<class T> void amin(T &a, T v) { if (a > v) a = v; }
template<class T> void amax(T &a, T v) { if (a < v) a = v; }
int ROUND(double x) { return (int)(x + 0.5); }
bool ISINT(double x) { return fabs(ROUND(x) - x) <= EPS; }
bool ISEQUAL(double x, double y) { return fabs(x - y) <= EPS*max(1.0, max(fabs(x), fabs(y))); }
double SQSUM(double x, double y) { return x*x + y*y; }
#define PI  (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
#define NG (-1)
#define BIG ((int)1e9+10)
#define BIGLL ((ll)4e18)
#define SZ(a) ((int)(a).size())
#define SQ(a) ((a)*(a))
typedef unsigned long long ull;
typedef long long ll;

struct PIECE
{
	char y[8];
	char x[8];
	char num;
	int score;
};

int main()
{
//	freopen("_google_code_jam_output.txt", "w", stdout);


	int H, W, K;
	scanf("%d %d %d", &H, &W, &K);

	vector <string> vs;
	for (int y = 0; y < H; y++)
	{
		string s;
		cin >> s;
		vs.push_back(s);
	}

	vector < vector <bool> > used(H, vector <bool>(W));



	// ベストな1個を探す

	vector <PIECE> answer;

	for (double minBaseScore = 7.0; minBaseScore>=1.0; )
	{
		// BEGIN CUT HERE
//		cout << " minBaseScore=" << minBaseScore << endl;
		// END CUT HERE



		// BEGIN CUT HERE
//		cout << " minBaseScore=" << minBaseScore << endl;
		// END CUT HERE



		queue < PIECE > q;

		for (int y = 0; y < H; y++)
		{
			for (int x = 0; x < W; x++)
			{
				if (!used[y][x])
				{
					// たぶん数字が低いところは突っ込まなくてよい。
					PIECE piece;
					piece.y[0] = y;
					piece.x[0] = x;
					piece.num = 1;
					piece.score = vs[y][x] - '0';

					q.push(piece);
				}
			}
		}
		int bestScore = NG;
		PIECE bestPiece;
		int numFinalPiece = 0;

		vector <int> minScore;
		for (int i = 0; i < K+1; ++i)
		{
			const int ms = pow(minBaseScore, i);
			minScore.push_back(ms);
//			cout << ms << endl;
		}

		while (!q.empty())
		{
			PIECE p = q.front();
			q.pop();

			// すべて1マス伸ばしてみる
			for (int i = 0; i < p.num; i++)
			{
				const char& y = p.y[i];
				const char& x = p.x[i];

				// 全方向に伸ばしてみる
				{
					const static int dy[] = { -1, 0, 1, 0 }; // U,R,D,L
					const static int dx[] = { 0, 1, 0,-1 };
					for (int d = 0; d < 4; ++d)
					{
						const int ny = y + dy[d];
						const int nx = x + dx[d];
						// 範囲内
						if (INRANGE(ny, 0, H - 1) && INRANGE(nx, 0, W - 1) && !used[ny][nx])
						{
							bool ok = true;
							// ただし同じマスを含んではいけない。
							for (int k = 0; k < p.num; k++)
							{
								if (ny == p.y[k] && nx == p.x[k])
								{
									ok = false;
									break;
								}
							}

							const int nextScore = p.score * (vs[ny][nx] - '0');

							if (ok && nextScore >= minScore[p.num + 1])
							{
								PIECE nextP = p;
								nextP.y[nextP.num] = ny;
								nextP.x[nextP.num] = nx;
								nextP.score = nextScore;
								nextP.num++;

								if (nextP.num == K)
								{
									numFinalPiece++;
									if (nextP.score > bestScore)
									{
										bestScore = nextP.score;
										bestPiece = nextP;
									}
								}
								else
								{
									q.push(nextP);
								}
							}
						}
					}
				}
			}
		}



		if (bestScore != NG)
		{
			answer.push_back(bestPiece);

//			// BEGIN CUT HERE
//			cerr << " numFinalPiece=" << numFinalPiece << endl;
//			// BEGIN CUT HERE
//			cout << " bestScore=" << bestScore << endl;
			for (int i = 0; i < K; i++)
			{
				const int y = bestPiece.y[i];
				const int x = bestPiece.x[i];
//				printf("y=%d x=%d num=%d\n", y, x, vs[y][x] - '0');


				used[y][x]=true;
			}
		}
		else
		{
			minBaseScore-= 0.2;
		}
	}

	cout << SZ(answer) << endl;
	for (int i=0;i<SZ(answer);++i)
	{
		for (int k = 0; k < K; k++)
		{
			printf("%d %d\n", 1+answer[i].y[k], 1+answer[i].x[k]);
		}
	}



	// END CUT HERE

	// END CUT HERE
















	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &H, &W, &K);
                               ^

Judge Result