O Hashiwokakero é um quebra-cabeça lógico japonês que literalmente significa "construa pontes!". O jogo é composto de um tabuleiro retangular quadriculado de tamanho arbitrário. Alguns quadrados são vazios e outros tem um círculo com um número entre 1 e 8, sendo esses chamados de ilhas. O objetivo é conectar todas as ilhas construindo pontes entre elas, seguindo algumas regras.
Laos estava brincando com esses puzzle e teve uma ideia de criar uma variação que chamou de Hashiwokakero Bicolor, com as seguintes regras:
Laos desenhou um exemplo de um tabuleiro de Hashiwokakero Bicolor que tem solução, mas ele ficou pensando se era possível fazer um programa de computador que pudesse lhe dizer isso.
Ajude Laos! Crie um programa que dado um tabuleiro de Hashiwokakero Bicolor, imprime se existe solução ou não.
A primeira linha contém dois inteiros: $$$N$$$ $$$(1 \le N \le 40)$$$ e $$$M$$$ $$$(1 \le M \le 40)$$$. As $$$N$$$ linhas a seguir descrevem o tabuleiro.
Cada linha do tabuleiro é composta de $$$M$$$ sequências de dois caracteres. As posições vazias são representadas por dois caracteres '.' da seguinte forma: '..'. Se a posição não for vazia, ela é composto por um caractere $$$D$$$ $$$(1 \le D \le 8)$$$ que representa o dígito, e um caractere $$$C$$$, que pode ser igual a 'a' se a posição for azul, ou 'b' se a posição for laranja.
Imprima 'YES' se existe uma solução para o tabuleiro, ou 'NO' se não existe.
7 7 2b3a..4b..2a.. 1a........2b2a ..1b....1b3a3b 2b....8a..5b2a 3b..3a........ ....2b....3a3b 3a....3b1a2b2a
YES