【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

相关文章

Knife4j+Axios+Redis前后端分离架构下的 API 管理与会话方案(最新推荐)

《Knife4j+Axios+Redis前后端分离架构下的API管理与会话方案(最新推荐)》本文主要介绍了Swagger与Knife4j的配置要点、前后端对接方法以及分布式Session实现原理,... 目录一、Swagger 与 Knife4j 的深度理解及配置要点Knife4j 配置关键要点1.Spri

使用Python实现可恢复式多线程下载器

《使用Python实现可恢复式多线程下载器》在数字时代,大文件下载已成为日常操作,本文将手把手教你用Python打造专业级下载器,实现断点续传,多线程加速,速度限制等功能,感兴趣的小伙伴可以了解下... 目录一、智能续传:从崩溃边缘抢救进度二、多线程加速:榨干网络带宽三、速度控制:做网络的好邻居四、终端交互

SQLite3 在嵌入式C环境中存储音频/视频文件的最优方案

《SQLite3在嵌入式C环境中存储音频/视频文件的最优方案》本文探讨了SQLite3在嵌入式C环境中存储音视频文件的优化方案,推荐采用文件路径存储结合元数据管理,兼顾效率与资源限制,小文件可使用B... 目录SQLite3 在嵌入式C环境中存储音频/视频文件的专业方案一、存储策略选择1. 直接存储 vs

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》:本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色(红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解

OpenCV实现实时颜色检测的示例

《OpenCV实现实时颜色检测的示例》本文主要介绍了OpenCV实现实时颜色检测的示例,通过HSV色彩空间转换和色调范围判断实现红黄绿蓝颜色检测,包含视频捕捉、区域标记、颜色分析等功能,具有一定的参考... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间

苹果macOS 26 Tahoe主题功能大升级:可定制图标/高亮文本/文件夹颜色

《苹果macOS26Tahoe主题功能大升级:可定制图标/高亮文本/文件夹颜色》在整体系统设计方面,macOS26采用了全新的玻璃质感视觉风格,应用于Dock栏、应用图标以及桌面小部件等多个界面... 科技媒体 MACRumors 昨日(6 月 13 日)发布博文,报道称在 macOS 26 Tahoe 中

SpringBoot服务获取Pod当前IP的两种方案

《SpringBoot服务获取Pod当前IP的两种方案》在Kubernetes集群中,SpringBoot服务获取Pod当前IP的方案主要有两种,通过环境变量注入或通过Java代码动态获取网络接口IP... 目录方案一:通过 Kubernetes Downward API 注入环境变量原理步骤方案二:通过

Springboot3+将ID转为JSON字符串的详细配置方案

《Springboot3+将ID转为JSON字符串的详细配置方案》:本文主要介绍纯后端实现Long/BigIntegerID转为JSON字符串的详细配置方案,s基于SpringBoot3+和Spr... 目录1. 添加依赖2. 全局 Jackson 配置3. 精准控制(可选)4. OpenAPI (Spri

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》:本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig

使用Python实现获取屏幕像素颜色值

《使用Python实现获取屏幕像素颜色值》这篇文章主要为大家详细介绍了如何使用Python实现获取屏幕像素颜色值,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、一个小工具,按住F10键,颜色值会跟着显示。完整代码import tkinter as tkimport pyau