五子棋判断 五子连珠

题目链接：https://ac.nowcoder.com/acm/contest/331/B
题目大意：

思路：因为N太大。二维数组肯定是开不下。所以用map存就可以了。

当时就去写了二百多行的代码，太暴力了。把五子棋所有可能形成五子连珠的情况都写出来的。

后来看了一些大佬的写法，找了简单的方法遍历五子棋的棋盘：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define p1 first
#define p2 second
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map

unordered_map<int, int> e[300005];
int dis[2][8]={-1, 1, 0, 0, 1, -1, -1, 1,
               -1, 1, 1,-1, 0,  0,  1,-1};
int n, m, x, y;

int dfs(int x, int y, int z)
{
    z=(z%2)?1:2;
    for(int i=0;i<8;i+=2)
    {
        int a=0, b=0;             //左侧与右侧的棋子数量

        int xx=x+dis[0][i], yy=y+dis[1][i];
        while(xx>=1&&xx<=n&&yy>=1&&yy<=n&&e[xx][yy]==z)
        {
            a++, xx+=dis[0][i], yy+=dis[1][i];
        }

        xx=x+dis[0][i+1], yy=y+dis[1][i+1];
        while(xx>=1&&xx<=n&&yy>=1&&yy<=n&&e[xx][yy]==z)
        {
            b++, xx+=dis[0][i+1], yy+=dis[1][i+1];
        }

        if(a+b>=4)               //>=4满足五子棋
        {
            return 1;
        }
    }

    return 0;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%c\n",(dfs(x, y, i))==1?'Y':'N');
        e[x][y]=(i%2)?1:2;
    }

    return 0;
}

原来的代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define p1 first
#define p2 second
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map

multimap<pair<int, int>, int> s1;
multimap<pair<int, int>, int> s2;

int dfs1(int x, int y)
{
    if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y-2))!=s1.end()&&s1.find(make_pair(x, y-3))!=s1.end()&&s1.find(make_pair(x, y-4))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y-2))!=s1.end()&&s1.find(make_pair(x, y-3))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y-2))!=s1.end()&&s1.find(make_pair(x, y+2))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x, y-1))!=s1.end()&&s1.find(make_pair(x, y+3))!=s1.end()&&s1.find(make_pair(x, y+2))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x, y+4))!=s1.end()&&s1.find(make_pair(x, y+3))!=s1.end()&&s1.find(make_pair(x, y+2))!=s1.end()&&s1.find(make_pair(x, y+1))!=s1.end())
    {
        return 1;
    }


    if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x-2, y))!=s1.end()&&s1.find(make_pair(x-3, y))!=s1.end()&&s1.find(make_pair(x-4, y))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x-2, y))!=s1.end()&&s1.find(make_pair(x-3, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x-2, y))!=s1.end()&&s1.find(make_pair(x+2, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y))!=s1.end()&&s1.find(make_pair(x+3, y))!=s1.end()&&s1.find(make_pair(x+2, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x+4, y))!=s1.end()&&s1.find(make_pair(x+3, y))!=s1.end()&&s1.find(make_pair(x+2, y))!=s1.end()&&s1.find(make_pair(x+1, y))!=s1.end())
    {
        return 1;
    }


    if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x-2, y-2))!=s1.end()&&s1.find(make_pair(x-3, y-3))!=s1.end()&&s1.find(make_pair(x-4, y-4))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x-2, y-2))!=s1.end()&&s1.find(make_pair(x-3, y-3))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x-2, y-2))!=s1.end()&&s1.find(make_pair(x+2, y+2))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y-1))!=s1.end()&&s1.find(make_pair(x+3, y+3))!=s1.end()&&s1.find(make_pair(x+2, y+2))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x+4, y+4))!=s1.end()&&s1.find(make_pair(x+3, y+3))!=s1.end()&&s1.find(make_pair(x+2, y+2))!=s1.end()&&s1.find(make_pair(x+1, y+1))!=s1.end())
    {
        return 1;
    }

    if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x-2, y+2))!=s1.end()&&s1.find(make_pair(x-3, y+3))!=s1.end()&&s1.find(make_pair(x-4, y+4))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x-2, y+2))!=s1.end()&&s1.find(make_pair(x-3, y+3))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x-2, y+2))!=s1.end()&&s1.find(make_pair(x+2, y-2))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x-1, y+1))!=s1.end()&&s1.find(make_pair(x+3, y-3))!=s1.end()&&s1.find(make_pair(x+2, y-2))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end())
    {
        return 1;
    }
    if(s1.find(make_pair(x+4, y-4))!=s1.end()&&s1.find(make_pair(x+3, y-3))!=s1.end()&&s1.find(make_pair(x+2, y-2))!=s1.end()&&s1.find(make_pair(x+1, y-1))!=s1.end())
    {
        return 1;
    }

    return 0;

}

int dfs2(int x, int y)
{
    if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y-2))!=s2.end()&&s2.find(make_pair(x, y-3))!=s2.end()&&s2.find(make_pair(x, y-4))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y-2))!=s2.end()&&s2.find(make_pair(x, y-3))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y-2))!=s2.end()&&s2.find(make_pair(x, y+2))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x, y-1))!=s2.end()&&s2.find(make_pair(x, y+3))!=s2.end()&&s2.find(make_pair(x, y+2))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x, y+4))!=s2.end()&&s2.find(make_pair(x, y+3))!=s2.end()&&s2.find(make_pair(x, y+2))!=s2.end()&&s2.find(make_pair(x, y+1))!=s2.end())
    {
        return 1;
    }


    if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x-2, y))!=s2.end()&&s2.find(make_pair(x-3, y))!=s2.end()&&s2.find(make_pair(x-4, y))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x-2, y))!=s2.end()&&s2.find(make_pair(x-3, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x-2, y))!=s2.end()&&s2.find(make_pair(x+2, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y))!=s2.end()&&s2.find(make_pair(x+3, y))!=s2.end()&&s2.find(make_pair(x+2, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x+4, y))!=s2.end()&&s2.find(make_pair(x+3, y))!=s2.end()&&s2.find(make_pair(x+2, y))!=s2.end()&&s2.find(make_pair(x+1, y))!=s2.end())
    {
        return 1;
    }


    if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x-2, y-2))!=s2.end()&&s2.find(make_pair(x-3, y-3))!=s2.end()&&s2.find(make_pair(x-4, y-4))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x-2, y-2))!=s2.end()&&s2.find(make_pair(x-3, y-3))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x-2, y-2))!=s2.end()&&s2.find(make_pair(x+2, y+2))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y-1))!=s2.end()&&s2.find(make_pair(x+3, y+3))!=s2.end()&&s2.find(make_pair(x+2, y+2))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x+4, y+4))!=s2.end()&&s2.find(make_pair(x+3, y+3))!=s2.end()&&s2.find(make_pair(x+2, y+2))!=s2.end()&&s2.find(make_pair(x+1, y+1))!=s2.end())
    {
        return 1;
    }

    if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x-2, y+2))!=s2.end()&&s2.find(make_pair(x-3, y+3))!=s2.end()&&s2.find(make_pair(x-4, y+4))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x-2, y+2))!=s2.end()&&s2.find(make_pair(x-3, y+3))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x-2, y+2))!=s2.end()&&s2.find(make_pair(x+2, y-2))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x-1, y+1))!=s2.end()&&s2.find(make_pair(x+3, y-3))!=s2.end()&&s2.find(make_pair(x+2, y-2))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end())
    {
        return 1;
    }
    if(s2.find(make_pair(x+4, y-4))!=s2.end()&&s2.find(make_pair(x+3, y-3))!=s2.end()&&s2.find(make_pair(x+2, y-2))!=s2.end()&&s2.find(make_pair(x+1, y-1))!=s2.end())
    {
        return 1;
    }

    return 0;

}

int main()
{
    int n, m, x, y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        if(i%2==1)
        {
            if(dfs1(x, y))
            {
                printf("Y\n");
                s1.insert(make_pair(make_pair(x, y), 1));
            }
            else
            {
                printf("N\n");
                s1.insert(make_pair(make_pair(x, y), 1));
            }
        }
        else
        {
            if(dfs2(x, y))
            {
                printf("Y\n");
                s2.insert(make_pair(make_pair(x, y), 1));
            }
            else
            {
                printf("N\n");
                s2.insert(make_pair(make_pair(x, y), 1));
            }
        }
    }

    return 0;

}