第七届传智杯 初赛 小红的四子棋 题解 简单bfs遍历
描述
小红和小紫正在下一个名字叫"四子棋"的游戏。游戏的规则如下：
棋盘是一个nn行mm列的矩阵，两人轮流下子。如果有一方出现横、竖或者斜对角线方向有4个或4个以上的相同颜色的连珠，则获得游戏胜利。
小红拿到了棋盘的终局，她想知道是谁获得了胜利。
输入描述：
第一行输入两个正整数 nn 和 mm，用空格隔开。
接下来的nn行，每行输入一个长度为mm的字符串，字符串仅由'r'、'p'和'.'三种字符组成。'r'代表小红的棋子，'p'代表小紫的棋子，'.'代表未落子。
保证'r'和'p'的数量之差的绝对值不超过1。
保证连珠不超过7个棋子。
保证不会两种颜色的棋子都连珠。
4≤n,m≤1004≤n,m≤100
输出描述：
如果小红获胜，则输出"kou"
如果小紫获胜，则输出"yukari"
如果暂时无人获胜，则输出"to be continued"
示例1
输入：
4 5 rpprr prrpp p.r.. p..r.
输出：
kou
说明：
小红连成了一个斜对角线方向的四连珠。
思路：
因为数据范围小，我们可以直接暴力遍历每一个点与四个方向的其他3个点是否可以连成4个相同的子（即以这一个点坐标为基准，8个方向分横，竖，右斜，左斜暴力遍历一次），判断输出答案即可。
我的代码:
#include <iostream> #include<queue> #include<algorithm> #include<map> #include<vector> #include<set> #include<stack> #include<string> #include<math.h> #include <iomanip> #include<unordered_map> #include <unordered_set> #include<array> #define gets(S) fgets(S,sizeof(S),stdin) #define ll long long const ll N = 2e6 + 5; const ll Max = 0x3f3f3f3f; using namespace std; ll n, m; char saki[1145][1145]; struct mjk{ ll x, y; }; queue<mjk>mzm; bool bfs(ll x, ll y) { if (saki[x][y] == '.')return 0; ll cnt = 0; for (int i = x - 3; i <= x + 3; i++) { if (i < 1 || i>n)continue; if (saki[i][y] == saki[x][y])cnt++; else cnt = 0; if (cnt == 4)return 1; } cnt = 0; for (int i = y - 3; i <= y + 3; i++) { if (i<1 || i>m)continue; if (saki[x][i] == saki[x][y])cnt++; else cnt = 0; if (cnt == 4)return 1; } cnt = 0; for (int i = x - 3, j = y - 3; i <= x + 3, j <= y + 3; i++, j++) { if (i < 1 || i>n || j<1 || j>m)continue; if (saki[i][j] == saki[x][y])cnt++; else cnt = 0; if (cnt == 4)return 1; } cnt = 0; for (int i = x + 3, j = y - 3; i <= x - 3, j <= y + 3; i--, j++) { if (i < 1 || i>n || j<1 || j>m)continue; if (saki[i][j] == saki[x][y])cnt++; else cnt = 0; if (cnt == 4)return 1; } return 0; } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> saki[i][j]; } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (bfs(i, j)) { cout << (saki[i][j] == 'r' ? "kou" : "yukari"); return 0; } } } cout << "to be continued"; return 0; }