-->The Game
直接中文
Descriptions:
判断五子棋棋局是否有胜者，有的话输出胜者的棋子类型，并且输出五个棋子中最左上的棋子坐标；没有胜者输出0。棋盘是这样的，如图
Sample Input
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Sample Output
1 3 2
题目链接：
https://vjudge.net/problem/POJ-1970
五子棋，但是有点小坑，不能六子连在一起，简单说就是只能5颗棋子在一起
从上到下、从左到右遍历棋盘，当位置(x, y)有棋子时，则从该位置开始dfs，加上搜索的方向为向右(x, y+1)，向下(x+1, y)，右下(x+1, y+1)，右上(x, y-1)，所以如果搜索的结果符合获胜的条件，则(x, y)就为最左上的位置。
除了坐标之外，还要加上方向vist[i][j][d]，表示在坐标(i, j)的d方向是否搜索过。
AC代码：
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 25 using namespace std; int T; int n=19; int cnt; int vis[Maxn][Maxn][Maxn];//vist[i][j][d] 坐标(i, j)的d方向是否搜索过 int mp[Maxn][Maxn];//棋盘 int dt[][2] = {{-1, 1}, {0, 1}, {1, 1}, {1, 0}}; //方向为右上、右、右下、下 void dfs(int x,int y,int k,int people)//（x,y） k方向 people哪个人的棋子 { vis[x][y][k]=1; int dx=x+dt[k][0]; int dy=y+dt[k][1]; if(dx>=1&&dy>=1&&dx<=n&&dy<=n&&mp[dx][dy]==people) { cnt++; dfs(dx,dy,k,people); } } int main() { cin>>T; while(T--) { int f=0;//初始化 MEM(vis,0); MEM(mp,0); for(int i=1; i<=n; i++)//存图 for(int j=1; j<=n; j++) cin>>mp[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(mp[i][j])//不为0，开始搜 { int people=mp[i][j];//看看是谁下的棋 for(int k=0;k<4;k++)//四个方向 { if(!vis[i][j][k]) { cnt=1;//棋子的个数 dfs(i,j,k,people); //5颗棋子，防止左上角之前还有一个棋子 if(cnt==5&&mp[i-dt[k][0]][j-dt[k][1]]!=people) { f=1; cout<<people<<endl; cout<<i<<" "<<j<<endl; break; } } } } } } if(f==0) cout<<"0"<<endl; } }