結果

問題 No.640 76本のトロンボーン
コンテスト
ユーザー newlife171128
提出日時 2018-02-04 20:52:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,950 bytes
コンパイル時間 1,463 ms
コンパイル使用メモリ 160,096 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-30 04:02:49
合計ジャッジ時間 3,543 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 2 RE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include "bits/stdc++.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <stdio.h>
#include <map>
#include <unordered_map>
#include <string.h>
#include <utility>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;

typedef pair<int, int> P;

int n;

int ans = 0;

char souko[76][76];
char mp[76][76];

void tate_nurinuri(int y, int x, char a) {
	for (int i = y; i <= y + n - 2; i++) {
		if (souko[i][x] == '.' && i < n) {
			souko[i][x] = a;
		}
	}
}
void yoko_nurinuri(int y, int x, char a) {
	for (int i = x; i <= x + n - 2; i++) {
		if (souko[y][i] == '.' && i < n) {
			souko[y][i] = a;
		}
	}
}

bool yoko_check(int y, int x, char a) {
	int cp = 0;
	for (int i = x; i <= x + n - 2; i++) {

		if (souko[y][i] == '.' && i < n) {
			cp++;
		}
	}

	if (cp == n - 1) {
		yoko_nurinuri(y, x, a);
		return true;
	} else {
		return false;
	}
}

bool tate_check(int y, int x, char a) {
	int cp = 0;
	for (int i = y; i <= y + n - 2; i++) {

		if (souko[i][x] == '.' && i < n) {
			cp++;
		}
	}

	if (cp == n - 1) {
		tate_nurinuri(y, x, a);
		return true;
	} else {
		return false;
	}
}

void yoko_dfs(int y, int x, char a, int ct) {
/*	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << souko[i][j];
		}
		cout << endl;
	}
	cout << endl;

	cout << ct << endl;*/

	ans = max(ans, ct);

	for (int i = y; i < n; i++) {
		for (int j = x; j < n; j++) {

			if (souko[i][j] == '.') {
				/*cout << "i" << i << " " << "j" << j << endl;*/
				if (yoko_check(i, j, a)) {

					/*cout << "横" << endl;*/
					yoko_dfs(0, 0, char(a + 1), ++ct);
				}
			}

		}

	}
}
void tate_dfs(int y, int x, char a, int ct) {
/*	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << souko[i][j];
		}
		cout << endl;
	}
	cout << endl;

	cout << ct << endl;*/

	ans = max(ans, ct);

	for (int i = y; i < n; i++) {
		for (int j = x; j < n; j++) {

			if (souko[i][j] == '.') {
				/*cout << "i" << i << " " << "j" << j << endl;*/
				if (tate_check(i, j, a)) {
					/*	cout << "縦" << endl;*/
					tate_dfs(0, 0, char(a + 1), ++ct);
				}
			}
		}
	}
}


void inite() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

			souko[i][j] = mp[i][j];

		}
	}
}

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char tmp;
			cin >> tmp;

			souko[i][j] = tmp;
			mp[i][j] = tmp;
		}
	}

	tate_dfs(0, 0, '1', 0);
	inite();
	yoko_dfs(0, 0, '1', 0);
	inite();
	if (tate_check(0, 0, 'T') || tate_check(0, n - 1, 'T')) {
		yoko_dfs(0, 0, '1', 1);

		inite();
	}
	if (yoko_check(0, 0, 'T') || yoko_check(n - 1, 0, 'T')) {
		tate_dfs(0, 0, '1', 1);

		inite();
	}

	if(tate_check(0, 0, 'T') && tate_check(1, n - 1, 'T')){
		yoko_dfs(0,0,'T',2);

		inite();
	}



	cout << ans << endl;
}
0