Codeforces 825B动态规划

题意

给出一张五子棋的图（此时双方都还没赢），求下一步能不能赢

分析

考虑右端点，dp[i][j][0]代表以（i，j）为右端点的全是X的最长长度，dp[i][j][1]代表以（i，j）为右端点的包含X和最多一个'.'的最长长度。

那么有：

若m[i][j]为X，则dp[i][j][0]=dp[i][j-1][0]+1,dp[i][j][1]=dp[i][j-1][1]+1；

若m[i][j]为'.'，则dp[i][j][0]=0,dp[i][j][1]=dp[i][j-1]+1；

若m[i][j]为O，则dp[i][j][0]=dp[i][j][1]=0。

胜利条件是dp[i][j][1]==5。

五子棋可以有四个方向，我们从左往右，从上往下扫描，分别枚举右端点，下端点，左下端点，右下端点就可以了。

代码

#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
char m[15][15];
int a[15][15][2]={0},b[15][15][2]={0},c[15][15][2]={0},d[15][15][2]={0};
bool ac(){
    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            if(m[i][j]!='O'){
                if(m[i][j]=='X'){
                    a[i][j][0]=a[i][j-1][0]+1;
                    a[i][j][1]=a[i][j-1][1]+1;
                    b[i][j][0]=b[i-1][j][0]+1;
                    b[i][j][1]=b[i-1][j][1]+1;
                    c[i][j][0]=c[i-1][j+1][0]+1;
                    c[i][j][1]=c[i-1][j+1][1]+1;
                    d[i][j][0]=d[i-1][j-1][0]+1;
                    d[i][j][1]=d[i-1][j-1][1]+1;
                }
                else if(m[i][j]=='.'){
                    a[i][j][1]=a[i][j-1][0]+1;
                    b[i][j][1]=b[i-1][j][0]+1;
                    c[i][j][1]=c[i-1][j+1][0]+1;
                    d[i][j][1]=d[i-1][j-1][0]+1;
                }
                if(a[i][j][0]==5||a[i][j][1]==5
                    ||b[i][j][0]==5||b[i][j][1]==5
                    ||c[i][j][0]==5||c[i][j][1]==5
                    ||d[i][j][0]==5||d[i][j][1]==5){
                    return true;
                }
            }
            
        }
    }
    return false;
}
int main(){
    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            cin>>m[i][j];
        }
    }
    printf(ac()?"YES\n":"NO\n");
    return 0;
}