{"problem":{"name":"[EC Final 2021] Check Pattern is Good","description":{"content":"Prof. Shou is given an $n\\times m$ board. Some cells are colored black, some cells are colored white, and others are uncolored. Prof. Shou likes **check patterns**, so he wants to color all uncolored","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":10000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9879"},"statements":[{"statement_type":"Markdown","content":"Prof. Shou is given an $n\\times m$ board. Some cells are colored black, some cells are colored white, and others are uncolored.\n\nProf. Shou likes **check patterns**, so he wants to color all uncolored cells and maximizes the number of check patterns on the board.\n\n$4$ cells forming a $2\\times 2$ square are said to have the check pattern if they are colored in one of the following ways:\n\n```plain\nBW\nWB\n```\n\n```plain\nWB\nBW\n```\n\nHere `W` (\"wakuda\" in Chewa language) means the cell is colored black and `B` (\"biancu\" in Corsican language) means the cell is colored white.\n\n## Input\n\nThe first line contains a single integer $T$ $(1\\leq T \\leq 10^4)$ denoting the number of test cases.\n\nThe first line of each test case contains two integers $n$ and $m$ ($1\\le n, m\\le 100$) denoting the dimensions of the board.\n\nEach of the next $n$ lines contains $m$ characters. The $j$-th character of the $i$-th line represents the status of the cell on the $i$-th row and $j$-th column of the board. The character is `W` if the cell is colored black, `B` if the cell is colored white, and `?` if the cell is uncolored. \n\nIt is guaranteed that the sum of $nm$ over all test cases is no more than $10^6$.\n\n## Output\n\nFor each test case, output a line containing the maximum number of check patterns on the board.\n\nIn the next $n$ lines, output the colored board in the same format as the input. The output board should satisfy the following conditions.\n\n- It consists of only `B` and `W`.\n- If a cell is already colored in the input, its color cannot be changed in the output.\n- The number of check patterns equals the answer you print.\n\nIf there are multiple solutions, output any of them.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9879","tags":["2021","网络流","Special Judge","O2优化","ICPC","EC Final"],"sample_group":[["3\n2 2\n??\n??\n3 3\nBW?\nW?B\n?BW\n3 3\nBW?\nW?W\n?W?\n","1\nWB\nBW\n1\nBWB\nWWB\nBBW\n4\nBWB\nWBW\nBWB\n"]],"created_at":"2026-03-03 11:09:25"}}