{"id":156,"date":"2017-02-20T14:28:03","date_gmt":"2017-02-20T17:28:03","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/competir\/?p=156"},"modified":"2017-02-22T10:54:13","modified_gmt":"2017-02-22T13:54:13","slug":"sudoku-seletiva-ime-2006","status":"publish","type":"post","link":"http:\/\/www.galirows.com.br\/meublog\/competir\/sudoku-seletiva-ime-2006\/","title":{"rendered":"Sudoku [Seletiva IME 2006]"},"content":{"rendered":"
\n

Seletiva para Maratona de Programa\u00e7\u00e3o do IME – 2006<\/em><\/p>\n

O jogo de Sudoku espalhou-se rapidamente por todo o mundo, tornando-se hoje o passatempo mais popular em todo o planeta. Muitas pessoas, entretanto, preenchem a matriz de forma incorreta, desrespeitando as restri\u00e7\u00f5es do jogo. Sua tarefa neste problema \u00e9 escrever um programa que verifica se uma matriz preenchida \u00e9 ou n\u00e3o uma solu\u00e7\u00e3o para o problema.<\/p>\n

A matriz do jogo \u00e9 uma matriz de inteiros 9 x 9 . Para ser uma solu\u00e7\u00e3o do problema, cada linha e coluna deve conter todos os n\u00fameros de 1 a 9. Al\u00e9m disso, se dividirmos a matriz em 9 regi\u00f5es 3 x 3, cada uma destas regi\u00f5es tamb\u00e9m deve conter os n\u00fameros de 1 a 9. O exemplo abaixo mostra uma matriz que \u00e9 uma solu\u00e7\u00e3o do problema.<\/p>\n

\"\"<\/a><\/p>\n<\/div>\n

<\/p>\n

Entrada<\/h2>\n
\n

S\u00e3o dadas v\u00e1rias inst\u00e2ncias. O primeiro dado \u00e9 o n\u00famero n<\/strong> > 0 de matrizes na entrada. Nas linhas seguintes s\u00e3o dadas as n<\/strong> matrizes. Cada matriz \u00e9 dada em 9 linhas, em que cada linha cont\u00e9m 9 n\u00fameros inteiros.<\/p>\n<\/div>\n

Sa\u00edda<\/h2>\n
\n

Para cada inst\u00e2ncia seu programa dever\u00e1 imprimir uma linha dizendo “Instancia k<\/strong><\/em>“, onde k<\/strong> \u00e9 o n\u00famero da inst\u00e2ncia atual. Na segunda linha, seu programa dever\u00e1 imprimir “SIM”<\/em> se a matriz for a solu\u00e7\u00e3o de um problema de Sudoku, e “NAO”<\/em> caso contr\u00e1rio. Imprima uma linha em branco ap\u00f3s cada inst\u00e2ncia.<\/p>\n<\/div>\n\n\n\n\n\n
Exemplo de Entrada<\/td>\nExemplo de Sa\u00edda<\/td>\n<\/tr>\n<\/thead>\n
2
\n1 3 2 5 7 9 4 6 8
\n4 9 8 2 6 1 3 7 5
\n7 5 6 3 8 4 2 1 9
\n6 4 3 1 5 8 7 9 2
\n5 2 1 7 9 3 8 4 6
\n9 8 7 4 2 6 5 3 1
\n2 1 4 9 3 5 6 8 7
\n3 6 5 8 1 7 9 2 4
\n8 7 9 6 4 2 1 5 3
\n1 3 2 5 7 9 4 6 8
\n4 9 8 2 6 1 3 7 5
\n7 5 6 3 8 4 2 1 9
\n6 4 3 1 5 8 7 9 2
\n5 2 1 7 9 3 8 4 6
\n9 8 7 4 2 6 5 3 1
\n2 1 4 9 3 5 6 8 7
\n3 6 5 8 1 7 9 2 4
\n8 7 9 6 4 2 1 3 5<\/td>\n		Instancia 1
\nSIMInstancia 2
\nNAO<\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

 <\/p>\n

 <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Solu\u00e7\u00e3o em C<\/strong><\/p>\n

#include <stdio.h>\r\n\r\nint main() {\r\n\tint k, i, j, temp, instancia = 0, solucao = 1;\r\n\tint matriz[9][9], somaLinha[9], somaColuna[9], somaMatriz[3][3];\r\n\r\n\tscanf(\"%i\", &k);\r\n\r\n    for(int cont = 0; cont < k; cont++) {\r\n    \t\/\/leitura de valores para a matriz\r\n\t\tfor(i = 0; i < 9; i++) {\r\n\t\t\tfor(j = 0; j < 9; j++) { \r\n\t\t\t\tscanf(\"%i\", &matriz[i][j]);\r\n\t\t\t}\r\n    \t}\r\n\r\n\t\t\/\/inicializa vari\u00e1veis somadoras com zero\r\n\t\tfor (i = 0; i < 9; i++) {\r\n\t\t\tsomaLinha[i]         = 0;\r\n\t\t\tsomaColuna[i]        = 0;\r\n\t\t\tsomaMatriz[i\/3][i%3] = 0;\r\n\t\t\t\/\/descomente o prinf abaixo para facilitar o entendimento sobre\r\n\t\t\t\/\/como a matriz est\u00e1 sendo preenchida sem utilizar dois for \r\n\t\t\t\/\/printf(\"%i %i \\n\", i\/3, i%3);\r\n\t\t}\r\n    \r\n    \t\/\/contabiliza valores para resolver o problema\r\n\t\tfor (i = 0; i < 9; i++) {\r\n\t\t\tfor (j = 0; j < 9; j++) {\r\n\t\t\t\ttemp = matriz[i][j] * matriz[i][j];\r\n\t\t\t\tsomaLinha[i]  += temp;\r\n\t\t\t\tsomaColuna[j] += temp;\r\n\t\t\t\tsomaMatriz[i\/3][j\/3] += temp;\r\n\t\t\t\t\/\/printf(\"%i %i %i %i %i\\n\", i, j, i\/3, j\/3, matriz[i][j]);\r\n\r\n\t\t\t\tif (i == 8 && somaColuna[j] != 285) { break; }\r\n\t\t\t} \r\n\r\n\t\t\tif (somaLinha[i] != 285) { break; }\r\n\t\t}\r\n\r\n\t\t\/\/mostra os resultados\r\n\t\tinstancia++;\r\n\t\tprintf(\"Instancia %i\\n\", instancia);\r\n\r\n\t\t\/\/determina se \u00e9 a solu\u00e7\u00e3o\r\n\t\tfor (int i = 0; i < 3; i++) {\r\n\t\t\tfor (int j = 0; j < 3; j++) {\r\n\t\t\t\tif (somaMatriz[i][j] != 285) {\r\n\t\t\t\t\tsolucao = 0;\r\n\t\t\t\t}\r\n\t\t\t}\r\n    \t}\r\n\r\n\t\tif (solucao == 1) {\r\n\t\t\tprintf(\"SIM\\n\\n\");\r\n\t\t} else {\r\n\t\t\tprintf(\"NAO\\n\\n\");\r\n\t\t}\r\n\r\n\t\tsolucao = 1;\r\n\t}\r\n          \r\n    return 0;\r\n}<\/pre>\n
Teste o c\u00f3digo em:<\/strong> http:\/\/ideone.com\/MBGDJq<\/a><\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
Seletiva para Maratona de Programa\u00e7\u00e3o do IME – 2006 O jogo de Sudoku espalhou-se rapidamente por todo o mundo, tornando-se hoje o passatempo mais popular em todo o planeta. Muitas pessoas, entretanto, preenchem a matriz de forma incorreta, desrespeitando as restri\u00e7\u00f5es do jogo. Sua tarefa neste problema \u00e9 escrever um programa que verifica se uma […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,7],"tags":[9],"class_list":["post-156","post","type-post","status-publish","format-standard","hentry","category-cc","category-maratona-de-programacao","tag-matriz"],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/156","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/comments?post=156"}],"version-history":[{"count":5,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/156\/revisions"}],"predecessor-version":[{"id":178,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/156\/revisions\/178"}],"wp:attachment":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/media?parent=156"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/categories?post=156"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/tags?post=156"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}