【2015-2016 XVI Open CupA】【贪心 确定性思想 正难则反 本身具有拓扑序】Abstract Picture 每行每列各染色一次 恢复颜色方案

本文主要是介绍【2015-2016 XVI Open CupA】【贪心 确定性思想 正难则反 本身具有拓扑序】Abstract Picture 每行每列各染色一次 恢复颜色方案,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

A. Abstract Picture
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Famous abstract painter Va Sya plans to start new painting. It will be composed as square with grid n × n, where each unit square is painted by some color.

Va Sya already defined the colors for some unit squares. Color of other squares does not matter for him.

For this work Va Sya is planning use the continuous technics: he paints whole row or whole column in some color. Moreover, each row and each column must be painted exactly once, so each unit square will be painted twice and its final color will be the last of two used colors.

Help Va Sya to find appropriate sequence of paints.

Input

First line of the input contains one integer n — length of the painting side in units (1 ≤ n ≤ 3000).

Each of the next n lines contains n characters. If i-th character in j-th line equals to '?', it means that color of i-th cell in j-th row of painting does not matter. Otherwise it contains lowercase English letter from 'a' to 'z' inclusively, which represents the color of corresponding cell (it is well known that Va Sya uses only 26 colors).

Output

Print 2n lines, i-th of those lines contains description of i-th paint in the following format:

«h y c» — row y is painted with color c;

«v x c» — column x is painted with color c.

Rows are numbered sequentially upside down, columns are numbered sequentially leftside right, so upper left corner is on intersection of row 1 and column 1. Each row and each column must be mentioned in the output exactly once.

You may assume that there exists at least one solution for the given input. If there are several correct solutions, print any of them.

Example
input
3
ac?
ab?
?cz
output
h 1 p
h 3 q
v 2 c
h 2 b
v 1 a
v 3 z
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 3030, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int n;
char a[N][N];
queue< pair<int,int> >q;
int sum[N + N];
int num[N + N][128];
pair<int,int> ans[N + N];
bool e[N + N];
void inq(int p, int c)
{q.push(MP(p, c));e[p] = 1;
}
void solve()
{while (!q.empty())q.pop();MS(e, 0);for (int i = 1; i <= n+n; ++i)if (sum[i]){for (char j = 'a'; j <= 'z'; ++j){if (num[i][j] == sum[i])inq(i, j);}}int o = n + n;while (!q.empty()){int p = q.front().first;int c = q.front().second;q.pop();ans[o--] = MP(p,c);if (p <= n)//行->列{for (int j = 1; j <= n; ++j)if(a[p][j]!='?'&&!e[j+n]){if (e[j + n])continue;--sum[j + n];--num[j + n][a[p][j]];if (sum[j + n])for (char k = 'a'; k <= 'z'; ++k){if (sum[j + n] == num[j + n][k])inq(j + n, k);}}}else//列->行{for (int i = 1; i <= n;++i)if(a[i][p-n]!='?')//一行行来{if (e[i])continue;--sum[i];--num[i][a[i][p - n]];if (sum[i] )for (char k = 'a'; k <= 'z';++k){if (sum[i] == num[i][k])inq(i,k);}}}}for (int i = n+n; i >= 1; --i)if (e[i] == 0)ans[o--] = MP(i, 'a');for (int i = 1; i <= n+n; ++i){if (ans[i].first <= n)printf("h %d %c\n", ans[i].first, ans[i].second);else printf("v %d %c\n", ans[i].first-n, ans[i].second);}
}
int main()
{while (~scanf("%d", &n)){MS(num, 0); MS(sum, 0);for (int i = 1; i <= n; ++i)scanf("%s", a[i]+1);for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j)if (a[i][j] != '?'){++sum[i];++num[i][a[i][j]];++sum[n+j];++num[n+j][a[i][j]];}}solve();}return 0;
}
/*
【trick&&吐槽】
1,这种sb题我竟然搞混了做法。
想了什么二分图匹配啦,网络流啦,拓扑排序啦一系列做法。
然而正解却是——
倒着来思考,直接按照确定性原则贪心选择就好了。2,写入队操作的时候没有把该行或列直接置否,导致了多次入队,崩盘>_<
果然是要把操作写得函数化的好。【题意】
给你一个n(3000)*n的正方形。
每个格子被涂了一定的颜色。
颜色一共只有'a'~'z'共计26种,
有些颜色任意,用'?'表示。涂色实际上恰好图了2n次,每行每列都涂色了一次。然而顺序和涂了什么色却不知道。
现在给你这个图,让你确定一种合法的涂色方案【类型】
贪心
遵循确定性原则分析问题【分析】
我们发现,我们最后一次涂色,该行或该列的颜色一定全部相同。
如果当前一行或一列的颜色完全相同,该行或列就可以是当前最后一次涂色的。
我们直接暴力,枚举所有行或列,取出所有可能是最后一次涂色的。
消除该次涂色对相应行或列的影响,并继续这个类似于拓扑排序的过程。
倒序输出,就可以AC了。【时间复杂度&&优化】
O(n^2*26)*/



这篇关于【2015-2016 XVI Open CupA】【贪心 确定性思想 正难则反 本身具有拓扑序】Abstract Picture 每行每列各染色一次 恢复颜色方案的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610412

相关文章

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Python 中的 with open文件操作的最佳实践

《Python中的withopen文件操作的最佳实践》在Python中,withopen()提供了一个简洁而安全的方式来处理文件操作,它不仅能确保文件在操作完成后自动关闭,还能处理文件操作中的异... 目录什么是 with open()?为什么使用 with open()?使用 with open() 进行

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比

SpringBoot首笔交易慢问题排查与优化方案

《SpringBoot首笔交易慢问题排查与优化方案》在我们的微服务项目中,遇到这样的问题:应用启动后,第一笔交易响应耗时高达4、5秒,而后续请求均能在毫秒级完成,这不仅触发监控告警,也极大影响了用户体... 目录问题背景排查步骤1. 日志分析2. 性能工具定位优化方案:提前预热各种资源1. Flowable

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

使用Python实现网络设备配置备份与恢复

《使用Python实现网络设备配置备份与恢复》网络设备配置备份与恢复在网络安全管理中起着至关重要的作用,本文为大家介绍了如何通过Python实现网络设备配置备份与恢复,需要的可以参考下... 目录一、网络设备配置备份与恢复的概念与重要性二、网络设备配置备份与恢复的分类三、python网络设备配置备份与恢复实

IDEA中Git版本回退的两种实现方案

《IDEA中Git版本回退的两种实现方案》作为开发者,代码版本回退是日常高频操作,IntelliJIDEA集成了强大的Git工具链,但面对reset和revert两种核心回退方案,许多开发者仍存在选择... 目录一、版本回退前置知识二、Reset方案:整体改写历史1、IDEA图形化操作(推荐)1.1、查看提