poj 1970(搜索)
2024-09-08 07:46:14
The Game
| Time Limit: 1000MS | Memory Limit: 30000K | |
| Total Submissions: 6247 | Accepted: 1601 |
Description
A game of Renju is played on a 19*19 board by two players. One player uses black stones and the other uses white stones. The game begins in an empty board and two players alternate in placing black stones and white stones. Black always goes first. There are 19 horizontal lines and 19 vertical lines in the board and the stones are placed on the intersections of the lines.
Horizontal lines are marked 1, 2, ..., 19 from up to down and vertical lines are marked 1, 2, ..., 19 from left to right.
The objective of this game is to put five stones of the same color
consecutively along a horizontal, vertical, or diagonal line. So, black
wins in the above figure. But, a player does not win the game if more
than five stones of the same color were put consecutively.
Given a configuration of the game, write a program to determine
whether white has won or black has won or nobody has won yet. There will
be no input data where the black and the white both win at the same
time. Also there will be no input data where the white or the black wins
in more than one place.
Input
The
first line of the input contains a single integer t (1 <= t <=
11), the number of test cases, followed by the input data for each test
case. Each test case consists of 19 lines, each having 19 numbers. A
black stone is denoted by 1, a white stone is denoted by 2, and 0
denotes no stone.
first line of the input contains a single integer t (1 <= t <=
11), the number of test cases, followed by the input data for each test
case. Each test case consists of 19 lines, each having 19 numbers. A
black stone is denoted by 1, a white stone is denoted by 2, and 0
denotes no stone.
Output
There
should be one or two line(s) per test case. In the first line of the
test case output, you should print 1 if black wins, 2 if white wins, and
0 if nobody wins yet. If black or white won, print in the second line
the horizontal line number and the vertical line number of the left-most
stone among the five consecutive stones. (Select the upper-most stone
if the five consecutive stones are located vertically.)
should be one or two line(s) per test case. In the first line of the
test case output, you should print 1 if black wins, 2 if white wins, and
0 if nobody wins yet. If black or white won, print in the second line
the horizontal line number and the vertical line number of the left-most
stone among the five consecutive stones. (Select the upper-most stone
if the five consecutive stones are located vertically.)
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
错了N次。。这个题坑点在于只能是五子棋，6子，7子都不行，所以对一个点的某一个方向来说正反都要搜一遍。
而且还要注意是结果是要位于左上角的点。所以可以先将某一列的每一行先找一遍，这样的话得到的结果就一定是左上角的点。
给大家两组测试用例：
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 1 2 0 0 0 0 0 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 0 0 0 0 0 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 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 1 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 2 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
答案是
1
6 1
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<queue>
#include<iostream>
using namespace std;
typedef long long LL;
int graph[][];
bool vis[][];
int cnt;
int res,resx,resy;
int dir[][] = {{,},{-,},{,},{,-},{,},{-,-},{-,},{,-}};
bool check(int x,int y,int flag)
{
if(x<||x>||y<||y>||graph[x][y]!=flag) return false;
return true;
}
struct Node
{
int x,y;
int step;
};
Node s;
bool bfs(int x,int y,int flag)
{
Node now;
now.x = x,now.y = y,now.step = ;
Node next;
for(int i=; i<; i++)
{
next.x = now.x+dir[i][];
next.y = now.y +dir[i][];
next.step = now.step+;
while(check(next.x,next.y,flag))
{
next.x+=dir[i][];
next.y+=dir[i][];
next.step++;
}
int step1 = next.step - ;
next.x = now.x+dir[i^][]; ///反方向也要找
next.y = now.y +dir[i^][];
next.step = now.step+;
while(check(next.x,next.y,flag))
{
next.x+=dir[i^][];
next.y+=dir[i^][];
next.step++;
}
int step2 = next.step - ;
if(step1+step2==) return true;
}
return false;
}
int main()
{
int tcase;
scanf("%d",&tcase);
while(tcase--)
{
for(int i=; i<; i++)
{
for(int j=; j<; j++)
{
scanf("%d",&graph[i][j]);
}
}
bool flag = false;
res = ,resx=-,resy=-;
for(int j=; j<&&!flag; j++)
{
for(int i=; i<&&!flag; i++)
{
if(graph[i][j]==)
{
flag = bfs(i,j,);
if(flag)
{
res = ;
resx = i;
resy = j;
}
}
if(graph[i][j]==)
{
flag = bfs(i,j,);
if(flag)
{
res = ;
resx = i;
resy = j;
}
}
}
}
if(res==) printf("0\n");
else printf("%d\n%d %d\n",res,resx,resy);
}
return ;
}
最新文章
- 【如何快速的开发一个完整的iOS直播app】(美颜篇)
- Visual Studio从此走入非Windows程序猿家
- .net重启iis线程池和iis站点程序代码【转】
- 简单易懂的现代魔法——Play Framework攻略4
- 转：CFile.Open()的使用说明
- Memcached基础
- ViewState的用法
- .NET - 代码重构技巧
- Android Jni引用第三方库
- python_变量的命名规则
- 微信小程序页面跳转 的几种方式
- MySQL MySql连接数与线程池
- Spirng MVC 重定向传递对象
- 【python】关于python中模块导入的总结
- Android硬件抽象层(HAL)深入剖析(二)【转】
- CSS中水平居中设置的几种方式
- 一个Servlet处理增删改查的方法
- Scrapy入门教程(转)
- JS关于浏览器尺寸的方法
- P2483 [SDOI2010]魔法猪学院