B. Ilya and tic-tac-toe game

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Ilya is an experienced player in tic-tac-toe on the4?×?4 field. He always starts and plays with Xs. He played a lot of games today with his friend Arseny. The friends became tired and didn't finish the last game. It was Ilya's turn in the game when they left it. Determine whether Ilya could have won the game by making single turn or not.

The rules of tic-tac-toe on the 4?×?4 field are as follows. Before the first turn all the field cells are empty. The two players take turns placing their signs into empty cells (the first player places Xs, the second player places Os). The player who places Xs goes first, the another one goes second. The winner is the player who first gets three of his signs in a row next to each other (horizontal, vertical or diagonal).

The tic-tac-toe position is given in four lines.

Each of these lines contains four characters. Each character is '.' (empty cell), 'x' (lowercase English letterx), or 'o' (lowercase English lettero). It is guaranteed that the position is reachable playing tic-tac-toe, and it is Ilya's turn now (in particular, it means that the game is not finished). It is possible that all the cells are empty, it means that the friends left without making single turn.

PRint single line: "YES" in case Ilya could have won by making single turn, and "NO" otherwise.

xx...oo.x...oox.Output
YESInput
x.oxox..x.o.oo.xOutput
NOInput
x..x..ooo...x.xoOutput
YESInput
o.x.o....x..ooxxOutput
NO
原題鏈接
題目大意：一個4*4的棋盤，以井字棋的規則，輸入棋局現狀，如果"x"下一步落子就能獲勝就打印"YES"，否則打印"NO"。
分析：
                  最壞落子情況有4*4=16種，每種情況共有12種獲勝情形（為端點8種，為中間點有4種），每種獲勝的情形需要判斷2個位置的情況，所以最壞復雜度為：16*12*4<1000, 因此只需要模擬下棋，將每種情況都考慮在內即可。
下面是AC代碼：（題目比較簡單但是代碼還是寫的比較繁瑣）
#include<iostream>#include<cstring>#include<math.h>#include<stdlib.h>#include<cstdio>#include<algorithm>using namespace std;char arr[4][4];bool solve(int a, int b){    int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};    int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};    for(int i=0; i<8; i++)    {        //這種情形可行（沒有越界）        if(a+dx[i]>=0&&a+dx[i]<=3 && b+dy[i]>=0&&b+dy[i]<=3 && a+2*dx[i]>=0&&a+2*dx[i]<=3 && b+2*dy[i]>=0&&b+2*dy[i]<=3)           if(arr[a+dx[i]][b+dy[i]]=='x' && arr[a+2*dx[i]][b+2*dy[i]]=='x')                return true;    }    for(int i=0; i<4; i++)    {        if(a+dx[i]>=0&&a+dx[i]<=3 && b+dy[i]>=0&&b+dy[i]<=3 && a+dx[i+4]>=0&&a+dx[i+4]<=3 && b+dy[i+4]>=0&&b+dy[i+4]<=3)            if(arr[a+dx[i]][b+dy[i]]=='x' && arr[a+dx[i+4]][b+dy[i+4]]=='x')                return true;    }    return false;}int main(void){    //freopen("input.txt","r",stdin);    while(scanf("%s", arr[0])!=EOF)    {        for(int i=0; i<3; i++)            scanf("%s", arr[i+1]);        int flag = 0;//變1表示確定獲勝        for(int i=0; i<4; i++)        {            for(int j=0; j<4; j++)            {                if(arr[i][j] == '.')//下一步下在這里                    if(solve(i,j))//確定輸贏                    {                        printf("YES/n");                        flag = 1;                        break;                    }            }            if(flag)//確定輸贏                break;        }        if(flag == 0)            printf("NO/n");    }    return 0;}如有不妥之處還望各位大佬不吝賜教，在下不勝感激。在此先行謝過。