Advertisement
Guest User

Untitled

a guest
Nov 27th, 2014
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <vector>
  5. #include <map>
  6. #define MAX_L 11
  7. using namespace std;
  8.  
  9. long long int Chave_Final;
  10. map <long long int,bool> Posicoes[MAX_L];
  11. vector <int> Estado_Actual;
  12. int Casos_Teste, N_Linhas, N_Colunas, Contador, Maior_Fila;
  13. char ch;
  14.  
  15. long long int Resolve(void){
  16.     long long int Chave_Actual = 0, Chave_Inicial;
  17.     for(int i = 0, m = 1; i < N_Linhas; i ++, m *= 10){ Chave_Actual += Estado_Actual[i] * m; }
  18.     if(Posicoes[N_Linhas].find(Chave_Actual) != Posicoes[N_Linhas].end()){ return Chave_Actual; }
  19.     Posicoes[N_Linhas][Chave_Actual] = false;
  20.     if(Estado_Actual[N_Linhas-1] == 0 && (N_Linhas == 1 || Estado_Actual[N_Linhas-2] == 0)){ return Chave_Actual; }
  21.     vector <int> Estado_Inicial = Estado_Actual;
  22.     Chave_Inicial = Chave_Actual;
  23.     bool Fim = false;
  24.     for(int r = Maior_Fila; r >= 0 && !Fim; r --){
  25.         for(int i = 0; i < N_Linhas; i ++){
  26.             if(i == (N_Linhas-1)){
  27.                 if(r <= Estado_Actual[i] && r > 0){
  28.                     Estado_Actual[i] = max(r-1, 0);
  29.                     Chave_Actual = Resolve();
  30.                     if(!Posicoes[N_Linhas][Chave_Actual]){ Posicoes[N_Linhas][Chave_Inicial] = true; Fim = true; break; }
  31.                 }
  32.             }
  33.             else{
  34.                 if(r < Estado_Actual[i]){
  35.                     Estado_Actual[i] = r;
  36.                     Chave_Actual = Resolve();
  37.                     if(!Posicoes[N_Linhas][Chave_Actual]){ Posicoes[N_Linhas][Chave_Inicial] = true; Fim = true; break; }
  38.                 }
  39.             }
  40.         }
  41.         Estado_Actual = Estado_Inicial;
  42.         Chave_Actual = Chave_Inicial;
  43.     }
  44.     return Chave_Actual;
  45. }
  46.  
  47. int main(void){
  48.  
  49.     scanf("%d", &Casos_Teste);
  50.     for(int caso = 1; caso <= Casos_Teste; caso ++){
  51.         Estado_Actual.clear();
  52.         scanf("%d %d", &N_Linhas, &N_Colunas);
  53.         for(int i = 0; i < N_Linhas; i ++){
  54.             Contador = 0; Maior_Fila = 0;
  55.             for(int j = 0; j < N_Colunas; j ++){
  56.                 scanf(" %c", &ch);
  57.                 if(ch == 'C'){ Contador ++; }
  58.             }
  59.             Estado_Actual.push_back(Contador);
  60.             if(Contador > Maior_Fila){ Maior_Fila = Contador; }
  61.         }
  62.         Chave_Final = Resolve();
  63.         if(Posicoes[N_Linhas][Chave_Final]){ printf("Case #%d: winning position\n", caso); }
  64.         else{ printf("Case #%d: losing position\n", caso); }
  65.     }
  66.  
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement