洛谷P1101 单词方阵【暴力】【字符串】

题目描述

给一n×nn \times nn×n的字母方阵,内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 888 个方向的任一方向,同一单词摆放时不再改变方向,单词与单词之间可以交叉,因此有可能共用字母。输出时,将不是单词的字母用*代替,以突出显示单词。例如:

输入:
8 输出:
qyizhong *yizhong
gydthkjy gy******
nwidghji n*i*****
orbzsfgz o**z****
hhgrhwth h***h***
zzzzzozo z****o**
iwdfrgng i*****n*
yyyygggg y******g

输入输出格式

输入格式:

第一行输入一个数nnn。(7≤n≤1007 \le n \le 1007≤n≤100)。

第二行开始输入n×nn \times nn×n的字母矩阵。

输出格式:

突出显示单词的n×nn \times nn×n矩阵。

输入输出样例

输入样例#1: 复制
7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
输出样例#1: 复制
*******
*******
*******
*******
*******
*******
*******
输入样例#2: 复制
8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg
输出样例#2: 复制
*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

题意:

给定一个n*n的字符矩阵,问能不能在行、列、对角线一共八个方向中找到字符串"yizhong"

把所有除"yizhong"之外的字符变成‘*’

思路:

数据量只有100,所以随便怎么暴力都行

 //#include<bits/stdc++>
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdlib.h>
#include<queue>
#include<map>
#include<stack>
#include<set> #define LL long long
#define ull unsigned long long
#define inf 0x3f3f3f3f using namespace std;
int n;
const int maxn = ;
string ch[maxn];
bool yes[maxn][maxn]; int main()
{
scanf("%d", &n);
for(int i = ; i < n; i++){
cin>>ch[i];
} for(int i = ; i < n; i++){
for(int j = ; j <= n - ; j++){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[i][j + k];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[i][j + k] = true;
}
}
}
for(int j = n - ; j >= ; j--){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[i][j - k];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[i][j - k] = true;
}
}
}
} for(int i = ; i < n; i++){
for(int j = ; j <= n - ; j++){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[j + k][i];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[j + k][i] = true;
}
}
}
for(int j = n - ; j >= ; j--){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[j - k][i];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[j - k][i] = true;
} }
}
} for(int i = ; i <= n - ; i++){
for(int j = -n + + i; j <= i; j++){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[i + k][i + k - j];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[i + k][i + k - j] = true;
}
}
}
}
for(int i = n - ; i >= ; i--){
for(int j = -n + + i; j <= i; j++){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[i - k][i - k - j];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[i - k][i - k - j] = true;
}
}
}
} for(int i = ; i <= n - ; i++){
for(int j = n - ; j >= ; j--){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[i + k][n - - i - k];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[i + k][n - - i - k] = true;
}
}
}
}
for(int i = n - ; i >= ; i--){
for(int j = ; j <= n - ; j++){
string tmp = "";
for(int k = ; k < ; k++){
tmp += ch[i - k][n - - i + k];
}
if(tmp == "yizhong"){
for(int k = ; k < ; k++){
yes[i - k][n - - i - k] = true;
} }
}
} for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(yes[i][j]){
printf("%c", ch[i][j]);
}
else{
printf("*");
}
}
printf("\n");
}
return ;
}
上一篇:[问题2014S03] 解答


下一篇:HDU5029--Relief grain (树链剖分+线段树 )