[编程题]五子棋
- 热度指数：1915 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
NowCoder最近爱上了五子棋，现在给你一个棋局，请你帮忙判断其中有没有五子连珠（超过五颗也算）。
输入描述:
输入有多组数据，每组数据为一张20x20的棋盘。
其中黑子用“*”表示，白子用“+”表示，空白位置用“.”表示。
输出描述:
如果棋盘上存在五子连珠（无论哪种颜色的棋子），输入“Yes”，否则输出“No”。
示例1
输入
.................... .................... .................... .................... ......*............. .......*............ ........*........... ....++++.*.......... ..........*......... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .......*............ ......+*+++......... .......*............ .......*............ .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ....................
输出
Yes No
使用卷积滤波的方式判断，一共有四种情况，这种方法简单明了，省略了大量的if判断循环语句。
对于边界采用padding扩展。
将棋盘转换为矩阵，分别存储白黑两种棋子的位置信息。
array_line = [[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]]
array_long = [[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0]]
array_slant1 = [[1, 0, 0, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1]]
array_slant2 = [[0, 0, 0, 0, 1],
[0, 0, 0, 1, 0],
[0, 0, 1, 0, 0],
[0, 1, 0, 0, 0],
[1, 0, 0, 0, 0]]
# 矩阵的点乘计算。返回乘积和
def matrixMul(A, B):
sum_value = 0
# res = [[0] * len(B[0]) for i in range(len(A))]
for i in range(len(A)):
for j in range(len(B[0])):
sum_value += A[i][j] * B[i][j]
return sum_value
# 提取子矩阵，用于与卷积滤波乘积。
def extract_sub_matrix(array, x, y, len):
sub_array = [[0 for i in range(len)] for i in range(len)]
for i in range(len):
for j in range(len):
sub_array[i][j] = array[i+x][j+y]
return sub_array
# 主逻辑
try:
while True:
# 初始化
array_B = [[0 for i in range(25)] for i in range(25)]
array_W = [[0 for i in range(25)] for i in range(25)]
draw = 1
count_B = 0
count_W = 0
#输入数据，棋盘信息存储到矩阵中。
for i in range(20):
temp = input()
for j in range(20):
if temp[j] == '*':
array_B[i+2][j+2] = 1
count_B = count_B + 1
elif temp[j] == '+':
array_W[i+2][j+2] = 1
count_W = count_W + 1
elif temp[j] == '.':
draw = 0
win_b = 0
win_w = 0
# 卷积运算，判定是否为五子棋棋盘。
for i in range(20):
for j in range(20):
#print("test")
if matrixMul(extract_sub_matrix(array_B,i,j, 5), array_line) == 5:
win_b = win_b + 1
if matrixMul(extract_sub_matrix(array_B,i,j, 5), array_long) == 5:
win_b = win_b + 1
if matrixMul(extract_sub_matrix(array_B,i,j, 5), array_slant1) == 5:
win_b = win_b + 1
if matrixMul(extract_sub_matrix(array_B,i,j, 5), array_slant2) == 5:
win_b = win_b + 1
for i in range(20):
for j in range(20):
if matrixMul(extract_sub_matrix(array_W,i,j, 5), array_line) == 5:
win_w = win_w + 1
if matrixMul(extract_sub_matrix(array_W,i,j, 5), array_long) == 5:
win_w = win_w + 1
if matrixMul(extract_sub_matrix(array_W,i,j, 5), array_slant1) == 5:
win_w = win_w + 1
if matrixMul(extract_sub_matrix(array_W,i,j, 5), array_slant2) == 5:
win_w = win_w + 1
#输出结果，对于有一方存在成功局面则Yes
if win_w >= 1 or win_b >= 1:
print("Yes")
else:
print("No")
except:
pass
编辑于 2018-09-28 14:22:06
回复(1)
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
using namespace std;
int main(int argc, char** argv)
{
//freopen("in.txt", "r", stdin);
vector<vector<char>> checkBoard(20, vector<char>(20));
char c;
while ((c = getchar()) != EOF)
{
ungetc(c,stdin);
for (int i = 0; i < 20; ++i)
{
for (int j = 0; j < 20; ++j)
{
c = getchar();
checkBoard[i][j] = c;
}
getchar();
}
bool found = false;
for (int i = 0; i < 20; ++i)
{
if (found) break;
for (int j = 0; j < 20; ++j)
{
if (checkBoard[i][j] == '.') continue;
c = checkBoard[i][j];
checkBoard[i][j] = '.';
int curCount = 1;
int x = i + 1;
while (x < 20 && checkBoard[x][j] == c)
{
checkBoard[x][j] = '.';
++curCount;
++x;
}
if (curCount >= 5)
{
found = true;
break;
}
curCount = 1;
int y = j + 1;
while (y < 20 && checkBoard[i][y] == c)
{
checkBoard[i][y] = '.';
++curCount;
++y;
}
if (curCount >= 5)
{
found = true;
break;
}
curCount = 1;
x = i + 1, y = j + 1;
while (x < 20 && y < 20 && checkBoard[x][y] == c)
{
checkBoard[x][y] = '.';
++curCount;
++x; ++y;
}
if (curCount >= 5)
{
found = true;
break;
}
}
}
if (found) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
发表于 2017-07-12 13:40:45
回复(2)
import java.util.*;
public class Main {
static int[][] direction = {{0, 1}, {0, - 1}, {1, 0}, { - 1, 0}, {1, 1}, {1, - 1}, { - 1, 1}, { - 1, - 1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
Character[][] map = new Character[20][20];
for (int i = 0; i < 20; i ++ ) {
String s = sc.next();
for (int j = 0; j < 20; j ++ ) {
map[i][j] = s.charAt(j);
}
}
if(check(map)) System.out.println("Yes");
else System.out.println("No");
}
}
public static boolean check(Character[][] map) {
for (int i = 0; i < 20; i ++ ) {
for (int j = 0; j < 20; j ++ ) {
if(map[i][j] == '*' || map[i][j] == '+') {
for (int k = 0; k < 8; k ++ ) {
int count = 1;
int x = i + direction[k][0];
int y = j + direction[k][1];
while (x >= 0 && x < 20 && y >= 0 && y < 20 && map[x][y] == map[i][j]) {
count ++ ;
x += direction[k][0];
y += direction[k][1];
}
if(count == 5) return true;
}
}
}
}
return false;
}
}
发表于 2016-10-14 01:37:48
回复(3)
#include<iostream>
#include<string>
using namespace std;
bool five(string v[])
{
for(int i = 0;i<20;i++)
{
for(int j = 0;j<20;j++)
{
if(v[i][j] == '.')//非棋子跳过
continue;
int right = 1,down = 1,right_down = 1,left_down = 1;
for(int t = 1;t<5;t++)//四个方向往后走四个
{
if(j<16 && v[i][j] == v[i][j+t])
right++;
if(i<16 && v[i][j] == v[i+t][j])
down++;
if(j<16 && i<16 && v[i][j] == v[i+t][j+t])
right_down++;
if(j>3 && i<16 && v[i][j] == v[i+t][j-t])
left_down++;
}
if(right == 5 || down == 5|| right_down == 5 ||left_down == 5)
return true;
}
}
return false;
}
int main()
{
string s[20];
while(cin>>s[0])
{
for(int i = 1;i<20;i++)
cin>>s[i];
cout << (five(s) ? "Yes" : "No") << endl;
}
return 0;
}
编辑于 2020-03-16 16:11:37
回复(0)
遇到一个棋子时，我们认为其是“五子”的第一颗，因此只需要再往右/下/右下遍历即可
#include <iostream>
#include <vector>
using namespace std;
bool check(vector<string>& board, int i, int j) {
if (i + 4 < 20) {
int k = 1;
for (; k <= 4; k++)
if (board[i + k][j] != board[i][j]) break;
if (k == 5) return true;
}
if (j + 4 < 20) {
int k = 1;
for (; k <= 4; k++)
if (board[i][j + k] != board[i][j]) break;
if (k == 5) return true;
}
if (i + 4 < 20 && j + 4 < 20) {
int k = 1;
for (; k <= 4; k++)
if (board[i + k][j + k] != board[i][j]) break;
if (k == 5) return true;
}
return false;
}
bool find(vector<string>& board) { // 找第一个
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
if (board[i][j] == '.') continue;
if (check(board, i, j)) return true;
}
}
return false;
}
int main() {
vector<string> board(20);
while (getline(cin, board[0])) {
for (int i = 1; i < 20; i++) {
getline(cin, board[i]);
}
if (find(board)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
发表于 2023-09-04 19:37:26
回复(0)
通过90%用例，这错误用例也看不了啊
#include <iostream>
#include<string>
#include<vector>
using namespace std;
int Countvv(char ch, int x, int y, vector<string>& vv) {
//上下
int count1 = 1;
int count2 = 1;
int i = 1;
while (true) { //上
if (x - i >= 0 && vv[x - i][y] == ch) {
count1++;
} else {
break;
}
i++;
}
i = 1;
while (true) {
if (x + i < 20 && vv[x + i][y] == ch) {
count2++;
} else {
break;
}
i++;
}
if (count1 + count2 - 1 == 5)
return 5;
//左右
count1 = 1;
count2 = 1;
i = 1;
while (true) { //左
if (y - i >= 0 && vv[x][y - i] == ch) {
count1++;
} else {
break;
}
i++;
}
i = 1;
while (true) { //右
if (y + i < 20 && vv[x][y + i] == ch) {
count2++;
} else {
break;
}
i++;
}
if (count1 + count2 - 1 == 5)
return 5;
//左上到右下
count1 = 1;
count2 = 1;
i = 1;
while (true) { //左上
if (y - i >= 0 && x - i >= 0 && vv[x - i][y - i] == ch) {
count1++;
} else {
break;
}
i++;
}
i = 1;
while (true) { //右下
if (y + i < 20 && x + i < 20 && vv[x + i][y + i] == ch) {
count2++;
} else {
break;
}
i++;
}
if (count1 + count2 - 1 == 5)
return 5;
//右上到左下
count1 = 1;
count2 = 1;
i = 1;
while (true) { //右上
if (y + i < 0 && x - i >= 0 && vv[x - i][y + i] == ch) {
count1++;
} else {
break;
}
i++;
}
i = 1;
while (true) { //左下
if (y - i >= 0 && x + i < 20 && vv[x + i][y - i] == ch) {
count2++;
} else {
break;
}
i++;
}
if (count1 + count2 - 1 == 5)
return 5;
return 0;
}
bool Count(vector<string>& vv) {
int count = 0;
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 20; j++) {
if (vv[i][j] == '+'||vv[i][j]=='*')
count = Countvv(vv[i][j], i, j, vv);
if (count == 5)
return true;
}
}
return false;
}
int main() {
string str;
while (cin >> str) {
vector<string> vv(20);
vv[0] = str;
for (int i = 1; i < 20; i++) {
cin >> vv[i];
}
string result = "No";
if (Count(vv))
result = "Yes";
cout << result << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")
编辑于 2023-03-26 22:23:10
回复(1)
//Ps：千万别看代码长，里面思路很清晰，比较无脑傻瓜式。很多都是重复的模版。每个分块上面有注释。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
char [][]cArr=new char[20][20];
int n=20;
int len=20;
int k=0;
while(n--!=0){
String str=in.next();
char[] cA = str.toCharArray();
cArr[k++]=cA;
}
// for (int i = 0; i < len; i++) {
// System.out.println(Arrays.toString(cArr[i]));
// }
boolean rsFlag=false;
//横向
for (int i = 0; i < len; i++) {
boolean flag=false;
int aste=0;
int plus=0;
for (int j = 0; j < len; j++) {
char c = cArr[i][j];
if(c=='*'){
aste++;
plus=0;
}
else if(c=='+'){
plus++;
aste=0;
}
else{
plus=0;
aste=0;
}
if(aste>=5 || plus>=5){
System.out.println("Yes");
rsFlag=true;
flag=true;
break;
}
}
if(flag){
break;
}
}
if(rsFlag){
continue;
}
//纵向
for (int i = 0; i < len; i++) {
boolean flag=false;
int aste=0;
int plus=0;
for (int j = 0; j < len; j++) {
char c = cArr[j][i];
if(c=='*'){
aste++;
plus=0;
}
else if(c=='+'){
plus++;
aste=0;
}
else{
plus=0;
aste=0;
}
if(aste>=5 || plus>=5){
System.out.println("Yes");
rsFlag=true;
flag=true;
break;
}
}
if(flag){
break;
}
}
if(rsFlag){
continue;
}
//斜-八字撇-正数20
for (int size = 1; size <= 20; size++) {
boolean flag=false;
int aste=0;
int plus=0;
for (int i = 0,j=size-1; i < size; i++,j--) {
char c=cArr[i][j];
if(c=='*'){
aste++;
plus=0;
}
else if(c=='+'){
plus++;
aste=0;
}
else{
plus=0;
aste=0;
}
if(aste>=5 || plus>=5){
System.out.println("Yes");
rsFlag=true;
flag=true;
break;
}
}
if(flag){
break;
}
}
if(rsFlag){
continue;
}
//斜-八字撇-倒数20
for (int size = 1; size <= 19; size++) {
boolean flag=false;
int aste=0;
int plus=0;
for (int i = 19,j=20-size; i > 19-size; i--,j++) {
char c=cArr[i][j];
if(c=='*'){
aste++;
plus=0;
}
else if(c=='+'){
plus++;
aste=0;
}
else{
plus=0;
aste=0;
}
if(aste>=5 || plus>=5){
System.out.println("Yes");
rsFlag=true;
flag=true;
break;
}
}
if(flag){
break;
}
}
if(rsFlag){
continue;
}
//斜-八字捺-正数20
for (int size = 1; size <= 20; size++) {
boolean flag=false;
int aste=0;
int plus=0;
for (int i = 0,j=20-size; i < size; i++,j++) {
char c=cArr[i][j];
if(c=='*'){
aste++;
plus=0;
}
else if(c=='+'){
plus++;
aste=0;
}
else{
plus=0;
aste=0;
}
if(aste>=5 || plus>=5){
System.out.println("Yes");
rsFlag=true;
flag=true;
break;
}
}
if(flag){
break;
}
}
if(rsFlag){
continue;
}
//斜-八字捺-倒数20
for (int size = 1; size <= 19; size++) {
boolean flag=false;
int aste=0;
int plus=0;
for (int i = 19,j=size-1; i > 19-size; i--,j--) {
char c=cArr[i][j];
if(c=='*'){
aste++;
plus=0;
}
else if(c=='+'){
plus++;
aste=0;
}
else{
plus=0;
aste=0;
}
if(aste>=5 || plus>=5){
System.out.println("Yes");
rsFlag=true;
flag=true;
break;
}
}
if(flag){
break;
}
}
if(rsFlag){
continue;
}
else{
System.out.println("No");
}
}
}
}
发表于 2016-10-14 13:56:37
回复(0)
import java.util.*;
公共类 Main {
final static int N = 20;
向（x，y）的八个方向进行搜索
static int count（char[][] map， char ch， int x， int y）{
int[][] direct = { {{ -1，0 }，{ 1，0 }}， // 上下
{{ 0，-1 }，{ 0，1 }}， // 左右
{{ -1，-1 }，{ 1，1 }}， // 左上、右下
{{ -1，1 }，{ 1，-1 }} }; // 右上、左下
int maxCount = 0;
for（int i = 0; i < 4; ++i）{ // 上下以及左右对角线
int c = 0;
for（int j = 0; j < 2; ++j）{
int nx = x;
int ny = y;
// 一直搜索，直到搜索到边界或者不等于+ 或者 *
while（nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] ==
ch）{
++c;
nx += direct[i][j][0];
ny += direct[i][j][1];
}
}
maxCount = Math.max（maxCount， c）;
}
// （x， y）位置计算了两次
返回 maxCount-1;
}
// 遍历map的每一个位置
public static boolean solve（char[][] map）{
for（int i = 0; i < N; ++i）{
for（int j = 0; j < N; ++j）{
// 如果该位置有符号，则进行搜索
if（'+' == map[i][j] ||'*' == map[i][j]）{
if（count（map， map[i][j]， i， j） >= 5）
return true;
}
}
} 返回
false;
}
public static void main（String args[]）{
// 循环处理多组测试用例
Scanner sc = new Scanner（System.in）;
while（sc.hasNext（））{
// 接收地图数据
char[][] map = new char[N][N];
for（int i = 0; i < N; ++i）{
map[i] = sc.next（）.toCharArray（）;
}
System.out.println（solve（map）？“是” ： “否”）;
}
}
}
公共类 Main {
final static int N = 20;
向（x，y）的八个方向进行搜索
static int count（char[][] map， char ch， int x， int y）{
int[][] direct = { {{ -1，0 }，{ 1，0 }}， // 上下
{{ 0，-1 }，{ 0，1 }}， // 左右
{{ -1，-1 }，{ 1，1 }}， // 左上、右下
{{ -1，1 }，{ 1，-1 }} }; // 右上、左下
int maxCount = 0;
for（int i = 0; i < 4; ++i）{ // 上下以及左右对角线
int c = 0;
for（int j = 0; j < 2; ++j）{
int nx = x;
int ny = y;
// 一直搜索，直到搜索到边界或者不等于+ 或者 *
while（nx >= 0 && nx < N && ny >= 0 && ny < N && map[nx][ny] ==
ch）{
++c;
nx += direct[i][j][0];
ny += direct[i][j][1];
}
}
maxCount = Math.max（maxCount， c）;
}
// （x， y）位置计算了两次
返回 maxCount-1;
}
// 遍历map的每一个位置
public static boolean solve（char[][] map）{
for（int i = 0; i < N; ++i）{
for（int j = 0; j < N; ++j）{
// 如果该位置有符号，则进行搜索
if（'+' == map[i][j] ||'*' == map[i][j]）{
if（count（map， map[i][j]， i， j） >= 5）
return true;
}
}
} 返回
false;
}
public static void main（String args[]）{
// 循环处理多组测试用例
Scanner sc = new Scanner（System.in）;
while（sc.hasNext（））{
// 接收地图数据
char[][] map = new char[N][N];
for（int i = 0; i < N; ++i）{
map[i] = sc.next（）.toCharArray（）;
}
System.out.println（solve（map）？“是” ： “否”）;
}
}
}
发表于 2022-07-08 16:43:43
回复(0)
卧槽。。为啥我完全看不懂评论区大佬们的算法。。。
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
final int X = 20;
final int Y = 20;
String[] map = new String[X];
while(sc.hasNext()){
for(int i = 0;i < X;i++){
map[i] = sc.nextLine();
}
boolean isYes = false;
out:for(int i = 0;i < X;i++){
for(int j = 0;j < Y;j++){
char ch = map[i].charAt(j);
if(ch == '.'){
continue;
}else if(ch == '*'){
int count = 1;
int i1 = i+1 , j1 = j+1;
while(i1 < X && map[i1].charAt(j) == '*'){
if(++count == 5){
System.out.println("Yes");
isYes = true;
break out;
}
i1++;
}
count = 1;
while(j1 < Y && map[i].charAt(j1) == '*'){
if(++count == 5){
System.out.println("Yes");
isYes = true;
break out;
}
j1++;
}
count = 1;
i1 = i+1;
j1 = j+1;
while(i1 < X && j1 < Y && map[i1].charAt(j1) == '*'){
if(++count == 5){
System.out.println("Yes");
isYes = true;
break out;
}
i1++;
j1++;
}
}else{
int count = 1;
int i1 = i+1 , j1 = j+1;
while(i1 < X && map[i1].charAt(j) == '+'){
if(++count == 5){
System.out.println("Yes");
isYes = true;
break out;
}
i1++;
}
count = 1;
while(j1 < Y && map[i].charAt(j1) == '+'){
if(++count == 5){
System.out.println("Yes");
isYes = true;
break out;
}
j1++;
}
count = 1;
i1 = i+1;
j1 = j+1;
while(i1 < X && j1 < Y && map[i1].charAt(j1) == '+'){
if(++count == 5){
System.out.println("Yes");
isYes = true;
break out;
}
i1++;
j1++;
}
}
}
}
if(!isYes){
System.out.println("No");
}
}
}
}
编辑于 2022-05-20 20:02:35
回复(0)
import java.util.*;
public class Main{
public static int[][] direc = {{0,1},{0,-1},{-1,0},{1,0},{-1,-1},{-1,1},{1,1},{1,-1}};
public static boolean solve(char[][] map){
for(int i = 0;i < 20;i++){
for(int j = 0;j < 20;j++){
if(map[i][j] == '*' || map[i][j] == '+'){
for(int k = 0;k < 8;k++){
int count = 1;
int x = i + direc[k][0];
int y = j + direc[k][1];
while(x >= 0 && x < 20 && y >= 0 && y <20 && map[i][j] == map[x][y]){
count++;
x = x + direc[k][0];
y = y + direc[k][1];
}
if(count == 5){
return true;
}
}
}
}
}
return false;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
char[][] map = new char[20][20];
for(int i = 0;i < 20;i++){
String s = sc.next();
for(int j = 0;j < 20;j++){
map[i][j] = s.charAt(j);
}
}
if(solve(map)){
System.out.println("Yes");
}else{
System.out.println("No");
}
}
}
} .
编辑于 2022-06-05 21:29:33
回复(0)
#include <iostream>
#include <vector>
using namespace std;
bool FiveGame(vector<string>& v)
{
for(int i = 0; i < 20; i++)
{
for(int j = 0; j < 20; j++)
{
if(v[i][j] == '.')
continue;
int right = 1;
int down = 1;
int right_down = 1;
int left_down = 1;
for(int k = 1; k < 5; k++)
{
if(i < 16 && v[i][j] == v[i + k][j])
down++;
if(j < 16 && v[i][j] == v[i][j + k])
right++;
if(i < 16 && j > 3 && v[i][j] == v[i + k][j - k])
left_down++;
if(i < 16 && j < 16 && v[i][j] == v[i + k][j + k])
right_down++;
}
if(right == 5 || down == 5 || right_down == 5 || left_down == 5)
return true;
}
}
return false;
}
int main()
{
vector<string> v(20);
while(cin >> v[0])
{
for(int i = 1; i < 20; i++)
cin >> v[i];
if(FiveGame(v))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
编辑于 2021-11-26 10:14:24
回复(0)
// 还就内个暴力解法
// 遍历棋盘，判断棋子的四个方向（右、右下、下、左下）
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String[] checkerboard = new String[20];
for(int i = 0; i < 20; i++){
checkerboard[i] = sc.next();
}
boolean result = false;
for(int i = 0; i < 20; i++){
for(int j = 0; j < 20; j++){
if(checkerboard[i].charAt(j) != '.'){
if(j < 16 && checkerboard[i].charAt(j) == checkerboard[i].charAt(j+1)
&& checkerboard[i].charAt(j) == checkerboard[i].charAt(j+2)
&& checkerboard[i].charAt(j) == checkerboard[i].charAt(j+3)
&& checkerboard[i].charAt(j) == checkerboard[i].charAt(j+4)){
result = true;
}
if(i < 16 && j < 16 && checkerboard[i].charAt(j) == checkerboard[i+1].charAt(j+1)
&& checkerboard[i].charAt(j) == checkerboard[i+2].charAt(j+2)
&& checkerboard[i].charAt(j) == checkerboard[i+3].charAt(j+3)
&& checkerboard[i].charAt(j) == checkerboard[i+4].charAt(j+4)){
result = true;
}
if(i < 16 && checkerboard[i].charAt(j) == checkerboard[i+1].charAt(j)
&& checkerboard[i].charAt(j) == checkerboard[i+2].charAt(j)
&& checkerboard[i].charAt(j) == checkerboard[i+3].charAt(j)
&& checkerboard[i].charAt(j) == checkerboard[i+4].charAt(j)){
result = true;
}
if(i < 16 && j > 3 && checkerboard[i].charAt(j) == checkerboard[i+1].charAt(j-1)
&& checkerboard[i].charAt(j) == checkerboard[i+2].charAt(j-2)
&& checkerboard[i].charAt(j) == checkerboard[i+3].charAt(j-3)
&& checkerboard[i].charAt(j) == checkerboard[i+4].charAt(j-4)){
result = true;
}
}
}
}
if(result){
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
}
发表于 2021-07-30 17:53:30
回复(0)
#include<cstdio>
(802)#include<iostream>
#include<cstring>
(803)#include<vector>
using namespace std;
int a[4][2]={{1,0},{0,1},{1,1},{1,-1}};
bool isright(vector<string> &v,int xi,int xj){
for(int i=0;i<4;++i){
int j;
for(j=0;j<5;++j){
int xxi=xi+a[i][0]*j;
int xxj=xj+a[i][1]*j;
if(xxi<0||xxi>=20||xxj<0||xxj>=20||v[xxi][xxj]!='*'){
break;
}
}
int k;
for(k=0;k<5;++k){
int xxi=xi+a[i][0]*k;
int xxj=xj+a[i][1]*k;
if(xxi<0||xxi>=20||xxj<0||xxj>=20||v[xxi][xxj]!='+'){
break;
}
}
if(j==5||k==5)
return true;
}
return false;
}
bool judge(vector<string> &v){
for(int i=0;i<20;++i){
for(int j=0;j<20;++j){
if(isright(v,i,j))
return true;
}
}
return false;
}
int main(){
vector<string> v;
v.resize(20);
while(cin>>v[0]){
for(int i=1;i<20;++i){
cin>>v[i];
}
if(judge(v)==true){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
发表于 2020-03-31 19:47:36
回复(0)
// write your code here cpp
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
bool JudgeFiveLine(char v[][20])
{
int dir[][2] = {{1, -1}, {1, 0}, {1, 1}, {0, 1}};
int count = 1;
for(int i = 0; i < 20; ++i)
for(int j = 0; j < 20; ++j)
{
if(v[i][j] == '.')
continue;
for(int m = 0; m < 4; m++)
{
if(i+4*dir[m][0]>=0&&i+4*dir[m][0]<20&&j+4*dir[m][1]>=0&&j+4*dir[m][1]<20)
{
for(int k = 1; k < 5; ++k)
{
if(v[i][j] == v[i+k*dir[m][0]][j+k*dir[m][1]])
++count;
}
}
if(count == 5)
return true;
count = 1;
}
}
return false;
}
int main()
{
int i = 0,
j = 0;
char map[20][20];
while(1)
{
for(i=0;i<20;i++)
{
for(j=0;j<20;j++)
{
if(scanf("%c",&map[i][j])==EOF)
return 0;
}
getchar();
}
printf("%s\n",JudgeFiveLine(map)?"Yes":"No");
}
return 0;
}
编辑于 2020-03-15 16:10:44
回复(0)
//简单的思路，复杂的代码，本地通过，牛客网无法通过
#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define BLACK '*'
#define WHITE '+'
#define WIDTH 20
#define HEIGHT 20
vector<string> vStr;
bool vertical(char c,int i,int j){
int temp = 0;
int sourceI = i+1;
//向上搜素带本身
while( i>=0 && vStr[i--][j] == c){
temp += 1;
}
//向下搜索
while(sourceI<=HEIGHT && vStr[sourceI++][j] == c){
temp += 1;
}
if(temp>=5)
return true;
else
return false;
}
bool level(char c,int i,int j){
int temp = 0;
int sourceJ = j+1;
//向左搜索
while( j>=0 && vStr[i][j--]==c){
temp += 1;
}
//向右搜索
while( sourceJ<=WIDTH && vStr[i][sourceJ++]==c){
temp += 1;
}
if(temp>=5)
return true;
else
return false;
}
bool leftup(char c,int i,int j){
int temp = 0;
int sourceI = i+1,sourceJ = j+1;
//向左上搜索
while( i>=0 && j>=0 && vStr[i--][j--] == c){
temp += 1;
}
//向右下搜索
while( sourceI<=HEIGHT && sourceJ<=WIDTH && vStr[sourceI++][sourceJ++]==c){
temp += 1;
}
if(temp>=5)
return true;
else
return false;
}
bool leftdown(char c,int i,int j){
int temp = 0;
int sourceI = i+1,sourceJ = j-1;
//向左下搜索
while( j>=0 && j<=WIDTH && vStr[i--][j++]==c){
temp += 1;
}
//向右上搜索
while( sourceI<=HEIGHT && sourceJ>=0 && vStr[sourceI++][sourceJ--]==c){
temp += 1;
}
if(temp>=5)
return true;
else
return false;
}
int main(){
string str;
for(int i =0 ;i<HEIGHT;i++){
getline(cin,str);
vStr.push_back(str);
}
for(unsigned int i=0;i<vStr.size();i++){
for(unsigned int j=0;j<vStr[0].size();j++){
if(vStr[i][j]==BLACK || vStr[i][j]==WHITE){
cout<<i<<","<<j<<" "<<vStr[i][j]<<endl;
if( vertical(vStr[i][j],i,j) || level(vStr[i][j],i,j)
|| leftup(vStr[i][j],i,j) || leftdown(vStr[i][j],i,j)){
cout<<"yes"<<endl;
return 0;
}
}
}
}
cout<<"NO"<<endl;
return 0;
}
发表于 2017-05-17 09:58:59
回复(2)
#include<iostream>
#include<string>
#define N 20
using namespace std;
string table[N]; //本题由于棋子是用字符表示的，所以非常适合用string数组表示
//对角线十字交叉判断是否有可能存在结果
bool crossJudge(string *table,int x,int y){
string s,str1(5,'.');
s.push_back(table[x-2][y-2]);
s.push_back(table[x-1][y-1]);
s.push_back(table[x][y]);
s.push_back(table[x+1][y+1]);
s.push_back(table[x+2][y+2]);
if(s==str1){
s.clear();
s.push_back(table[x][y]);
s.push_back(table[x-2][y+2]);
s.push_back(table[x-1][y+1]);
s.push_back(table[x+1][y-1]);
s.push_back(table[x+2][y-2]);
if(s==str1){
return false; //不可能存在结果，pass
}else{
return true;
}
}else{
return true; //可能存在结果
}
}
bool judgeResult(string *table,int x,int y){ //在一个5*5的领域内判断
int row1=x-2,row2=x+2;
string str1(5,'*');
string str2(5,'+');
for(int i=row1;i<=row2;i++){ //注意边界，取等号很关键
string s=table[i].substr(y-2,5);
if(s==str1||s==str2){
return true;
}
}
int col1=y-2,col2=y+2;
string s;
for(int i=col1;i<=col2;i++){
s.clear(); //每轮循环记得清空
s.push_back(table[y-2][i]);
s.push_back(table[y-1][i]);
s.push_back(table[y][i]);
s.push_back(table[y+1][i]);
s.push_back(table[y+2][i]);
if(s==str1||s==str2){
return true;
}
}
//交叉判断
s.clear();
s.push_back(table[x-2][y-2]);
s.push_back(table[x-1][y-1]);
s.push_back(table[x][y]);
s.push_back(table[x+1][y+1]);
s.push_back(table[x+2][y+2]);
if(s==str1||s==str2)return true;
s.clear();
s.push_back(table[x-2][y+2]);
s.push_back(table[x-1][y+1]);
s.push_back(table[x][y]);
s.push_back(table[x+1][y-1]);
s.push_back(table[x+2][y-2]);
if(s==str1||s==str2)return true;
return false;
}
int main(){ //（0ms 8552k）
while(cin>>table[0]){
for(int i=1;i<N;i++){
cin>>table[i];
}
//开始判断
int edge=N-2;
bool res=false;
for(int i=2;i<edge;i++){
for(int j=2;j<edge;j++){
if(crossJudge(table,i,j)){ //需进一步判断
res = judgeResult(table,i,j);
if(res){
cout<<"Yes"<<endl;
break;
}
}
}
if(res)break;
}
if(!res)cout<<"No"<<endl;
}
return 0;
}
发表于 2016-06-30 11:14:38
回复(0)
沿着8个方向搜就好了。。。
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
#define N 20
int count(string table[], char ch, int x, int y)
{
int maxc = 0;
int dir[4][2][2] = { {{ -1,0 },{ 1,0 }},{{ 0,-1 },{ 0,1 }},{{ -1,-1 },{ 1,1 }},{{ -1,1 },{ 1,-1 }} };
for (int i = 0; i < 4; ++i) // 四种方向
{
int c = 0;
for (int j = 0; j < 2; ++j) // 两个小方向
{
int nx = x, ny = y;
while (nx >= 0 && nx < N && ny >= 0 && ny < N && table[nx][ny] == ch)
{
nx += dir[i][j][0];
ny += dir[i][j][1];
++c;
}
}
maxc = (maxc > c ? maxc : c);
}
return maxc - 1;
}
bool solve(string table[])
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (table[i][j] == '*' || table[i][j] == '+')
if (count(table, table[i][j], i, j) >= 5)
return true;
}
}
return false;
}
int main()
{
string table[N];
while (cin >> table[0])
{
for (int i = 1; i < N; ++i) cin >> table[i];
cout << (solve(table) ? "Yes" : "No") << endl;
}
return 0;
}
发表于 2015-12-20 15:54:11
回复(0)
问题信息
难度：
18条回答
22收藏
12930浏览
通过挑战的用户
查看代码-
2023-02-09 23:09:30 -
2023-01-10 11:48:46
-
2023-01-05 21:44:31 -
2022-12-25 18:29:19
-
2022-12-23 17:40:42
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
