Problem A
Fill the Square
Input:Standard Input
Output:Standard Output
In this problem, you have to draw a square using uppercase English Alphabets.
To be more precise, you will be given a square grid with some empty blocks and others already filled for you with some letters to make your task easier. You have to insert characters in every empty cell so that the whole grid is filled with alphabets. In
doing so you have to meet the following rules:
- Make sure no adjacent cells contain the same letter; two cells are adjacent if they share a common edge.
- There could be many ways to fill the grid. You have to ensure you make the lexicographically smallest one. Here, two grids are checked in row major order when comparing lexicographically.
Input
The first line of input will contain an integer that will determine the number of test cases. Each case starts with an integern( n<=10 ),that represents the dimension of the grid. The nextnlines will containncharacters
each. Every cell of the grid is either a ‘.’ or a letter from [A, Z]. Here a ‘.’ Represents an empty cell.
Output
For each case, first output Case #: ( # replaced by case number ) and in the next n lines output the input matrix with the empty cells filled heeding the rules above.
Sample Input Output for Sample Input
2
3
...
...
...
3
...
A..
...
|
Case 1:
ABA
BAB
ABA
Case 2:
BAB
ABA
BAB
|
题意:给定一个map,要填充使得字典序最小。求填充之后样子。
思路:每个去填充的时候,都找个最小的去填充即可。
代码:
#include <stdio.h>
#include <string.h>
#define max(a,b) (a)>(b)?(a):(b)
const int d[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int N = 15;
int t, n;
char g[N][N];
void init() {
scanf("%d", &n);
for (int i = 0; i < n; i ++)
scanf("%s", g[i]);
}
bool judge(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < n)
return true;
return false;
}
bool judge2(int i, int x, int y) {
for (int j = 0; j < 4; j ++) {
int xx = x + d[j][0];
int yy = y + d[j][1];
if (judge(xx, yy)) {
if (i + 'A' == g[xx][yy])
return false;
}
}
return true;
}
char find(int x, int y) {
for (int i = 0; i < 26; i ++) {
if (judge2(i, x, y))
return i + 'A';
}
}
void solve() {
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (g[i][j] == '.')
g[i][j] = find(i, j);
printf("%c", g[i][j]);
}
printf("\n");
}
}
int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
init();
printf("Case %d:\n", ++cas);
solve();
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC