Решение задачи Игра с пешкой с Acmp

Без пояснения   Просмотров: 194


В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a1, a2, …, aN. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

Код

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n, b;
    cin >> n;
    int a[n][n];
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j)
            a[i][j] = 0;
    }
    for(int i = 0; i < n; ++i){
        cin >> b;
        a[i][i] = b;
    }
    if(n % 2)
    for(int i = 1; i < n; ++i){
        if(i % 2)
            for(int j = i, t = 0; j < n; ++j, ++t){
                a[j][t] = min(a[j - 1][t], a[j][t + 1]);
            }
        else{
            for(int j = i, t = 0; j < n; ++j, ++t){
                a[j][t] = max(a[j - 1][t], a[j][t + 1]);
            }
        }
    }
    else
    for(int i = 1; i < n; ++i){
        if(i % 2)
            for(int j = i, t = 0; j < n; ++j, ++t){
                a[j][t] = max(a[j - 1][t], a[j][t + 1]);
            }
        else{
            for(int j = i, t = 0; j < n; ++j, ++t){
                a[j][t] = min(a[j - 1][t], a[j][t + 1]);
            }
        }
    }
 
    int i = n - 1;
    int j = 0;
    b = 0;
    while(i != j){
        if(b % 2 == 0){
            if(a[i - 1][j] > a[i][j + 1])
                --i;
            else
                ++j;
        }
        else{
            if(a[i - 1][j] > a[i][j + 1])
                ++j;
            else
                --i;
        }
        ++b;
    }
    cout << a[i][j];
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться