题目链接：http://poj.org/problem?id=1970
题意：
有一个19 × 19 的五子棋棋盘，其中“0”代表未放入棋子，“1”代表黑色棋子，”2“代表白色棋子，如果某方的棋子在横，纵，斜这四个方向的连子数(连着的棋子数)恰好为5,那么此方就可以获胜。给你某一刻棋盘上的棋子状态，问你在此刻是哪一方获胜，亦或是平局，平局时仅输出“0”;如果是黑色方获胜，那么输出“1“,白色方获胜输出“2”，并且在第二行输出五连子最左边的棋子的坐标，如果在纵方向五连子，那么输出最上面的那个棋子的坐标。
思路：
首先，对于一个棋子来说，它可以和八个方向的棋子连在一起形成连子，但是这里并用不着对棋子的八个方向进行搜索，因为八个方向实质上可以认为是四个方向，即只需对某个棋子的四个方向进行搜索就OK 了，方向的选择也会影响到程序的复杂性，这里的做法是选择一个当前棋子作为起点(0,0)，对这个棋子的”“右上”(-1,1)，“右”(0,1)，“右下”(1,1)，“下”(1,0)这四个方向进行搜索，原因是如果这四个方向能找到五连子，那么作为起点的棋子的坐标即是题目要求的最左边的棋子的坐标，可以降低程序复杂性。方向确定了，搜索的状态就确定了，对于每个棋子有四个状态，所以又需要一个辅助数组来标记棋子的某个状态是否已被搜索过，用一个三维数组visit[i][j][k]代表坐标为(i, j)的棋子其k方向是否已被搜索过，k取值为1～4。然后从左到右、从上到下遍历图，分别从四个方向搜索统计就好了。
由于“右上”方向在搜索中的特殊性，所以这里要解释一些东西。在往“右上”方向搜索的过程中，如果一个棋子的“右上”方向没被搜索过，那么应该尽可能的往这个方向搜索(即使这个方向的其他棋子之前已被搜索过了，这里仍然要进行搜索)。
比如：
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...
...
首先搜索到的肯定是第一行的”1“,可知连子数为 1个, 但此时并不满足; 再搜索第二行的“1”，此时第一行的1虽然已经搜索过了，但是还需要再搜索一遍，可得连子数为2个; 当搜索到第三行的"1"时，上面的两个"1"仍然要进行搜索统计，可得连子数为3个......底下的两个“1”也是同理，虽然这里可以用记忆化，但是由于搜索树的层数并不深，所以影响不大。
然后当“右上”方向的延伸结果为5时，这里还需要判断“右上”这个方向的反方向(即右下)有没有一样的棋子(否则会出现6连子，不符合题意)，之所以要判断“右上”的反方向是否有多余的棋子，是因为位于“右下”的棋子搜索顺序在当前棋子之后，所以“右下”若有相同的棋子，有可能使得本来的5连子形成6连子，但是“右”的反方向“左”、“右下”的反方向“右上”、"下"的反方向“上”，这三个反方向上的棋子的搜索顺序都在当前棋子之前，不用考虑是否会出现这个现象。
代码：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <queue>
#include <algorithm>
#include <string> typedef long long LL;
using namespace std;
const int MAXN = ;
const int stepX[] = {, -, , , };//四个方向
const int stepY[] = {, , , , };
int visit[MAXN + ][MAXN + ][];//visit[i][j][k]表示位于[i][j]位置的棋子的k方向是否已被搜索过
int map[MAXN + ][MAXN + ];//存图
int cnt; void DFS(int x, int y, int id, int dire) {//x,y为坐标，id为1或者2,dire代表方位，即确定方位的进行搜索
visit[x][y][dire] = ;
int nex = x + stepX[dire], ney = y + stepY[dire];
if(map[nex][ney] == id){
++cnt;//统计连子数
DFS(nex, ney, id, dire);
}
} int main() {
//freopen("input", "r", stdin);
int t;
scanf("%d", &t);
while(t--) {
memset(visit, , sizeof(visit));
memset(map, , sizeof(map));
cnt = ;
for(int i = ; i <= ; i++) {
for(int j = ; j <= ; j++) {
scanf("%d", &map[i][j]);
}
}
int leftX = -, leftY = -;//五连子最左边棋子的坐标
int win = ;//获胜的标志
for(int i = ; i <= ; i++) {
for(int j = ; j <= ; j++) {
if(!map[i][j]) continue;
for(int k = ; k <= ; k++) {
if(!visit[i][j][k]) {
cnt = ;
DFS(i, j, map[i][j], k);
if(cnt == && map[i - stepX[k]][j - stepY[k]] != map[i][j]) {//判断是否为五连子且考虑反方向是否会造成六连子
win = map[i][j], leftX = i, leftY = j;
}
}
}
}
}
printf("%d\n", win);
if(win) printf("%d %d\n", leftX, leftY);
}
return ;
}