Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- #include <stdio.h>
- #include <vector>
- #include <map>
- #define MAX_L 11
- using namespace std;
- long long int Chave_Final;
- map <long long int,bool> Posicoes[MAX_L];
- vector <int> Estado_Actual;
- int Casos_Teste, N_Linhas, N_Colunas, Contador, Maior_Fila;
- char ch;
- long long int Resolve(void){
- long long int Chave_Actual = 0, Chave_Inicial;
- for(int i = 0, m = 1; i < N_Linhas; i ++, m *= 10){ Chave_Actual += Estado_Actual[i] * m; }
- if(Posicoes[N_Linhas].find(Chave_Actual) != Posicoes[N_Linhas].end()){ return Chave_Actual; }
- Posicoes[N_Linhas][Chave_Actual] = false;
- if(Estado_Actual[N_Linhas-1] == 0 && (N_Linhas == 1 || Estado_Actual[N_Linhas-2] == 0)){ return Chave_Actual; }
- vector <int> Estado_Inicial = Estado_Actual;
- Chave_Inicial = Chave_Actual;
- bool Fim = false;
- for(int r = Maior_Fila; r >= 0 && !Fim; r --){
- for(int i = 0; i < N_Linhas; i ++){
- if(i == (N_Linhas-1)){
- if(r <= Estado_Actual[i] && r > 0){
- Estado_Actual[i] = max(r-1, 0);
- Chave_Actual = Resolve();
- if(!Posicoes[N_Linhas][Chave_Actual]){ Posicoes[N_Linhas][Chave_Inicial] = true; Fim = true; break; }
- }
- }
- else{
- if(r < Estado_Actual[i]){
- Estado_Actual[i] = r;
- Chave_Actual = Resolve();
- if(!Posicoes[N_Linhas][Chave_Actual]){ Posicoes[N_Linhas][Chave_Inicial] = true; Fim = true; break; }
- }
- }
- }
- Estado_Actual = Estado_Inicial;
- Chave_Actual = Chave_Inicial;
- }
- return Chave_Actual;
- }
- int main(void){
- scanf("%d", &Casos_Teste);
- for(int caso = 1; caso <= Casos_Teste; caso ++){
- Estado_Actual.clear();
- scanf("%d %d", &N_Linhas, &N_Colunas);
- for(int i = 0; i < N_Linhas; i ++){
- Contador = 0; Maior_Fila = 0;
- for(int j = 0; j < N_Colunas; j ++){
- scanf(" %c", &ch);
- if(ch == 'C'){ Contador ++; }
- }
- Estado_Actual.push_back(Contador);
- if(Contador > Maior_Fila){ Maior_Fila = Contador; }
- }
- Chave_Final = Resolve();
- if(Posicoes[N_Linhas][Chave_Final]){ printf("Case #%d: winning position\n", caso); }
- else{ printf("Case #%d: losing position\n", caso); }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement