한번 제 나름대로 코드를 짜봤는데 제 생각이 틀려 오답이 나온것 같아서 다른 분들의 의견을 여쭙고자 합니다.. ㅠㅠ

twoBlock, threeBlock -> 현재 칸을 포함했다는 전제하에 2칸 3칸 블럭을 놓을수 있는 위치들을 저장

status -> 이진수로 25칸 배열의 상태를 나타내어 전달함.

전체적인 알고리즘 설명:

int game(state):
1. state를 토대로 판을 재구성
2. 판에서 새로 놓을수 없다면 패배
3. 새로 놓을 수 있다면, 가능한 모든 곳들을 두어보며 성공할 수 있는 신의 한수가 있다면 즉시 성공을 리턴
4. 신의한수가 한번도 없었다면 패배를 리턴

#include<iostream>
using namespace std;

char cache[1<<25];
bool board[5][5];
int twoBlock[2][2] = { {0, 1}, {1, 0} };//현재칸 포함, 아래칸도 비었거나, 옆에칸도 비었거나
int threeBlock[3][2][2] = { {{0, 1},{1, 0}}, {{1, 0},{1, 1}}, {{0, 1},{1, 1}} };//현재칸 포함해서 가능한 ㄱ, ㄴ모양들

bool insideBoard(int x, int y) {//경계 밖을 나갔는지 확인
    if (x >= 0 && x < 5 && y >= 0 && y < 5) return true;
    return false;
}
bool isLose() {
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            if (!board[i][j]) {//판 처음부터 끝까지 2칸짜리나 3칸짜리 블럭을 놓을수 있는지 확인
                for (int k = 0; k < 2; k++) {
                    int x = i + twoBlock[k][0];
                    int y = j + twoBlock[k][1];
                    if (insideBoard(x, y) && !board[x][y]) return false;
                }
                for (int k = 0; k < 3; k++) {
                    int x1 = i + threeBlock[k][0][0];
                    int y1 = j + threeBlock[k][0][1];
                    int x2 = i + threeBlock[k][1][0];
                    int y2 = j + threeBlock[k][1][1];
                    if (insideBoard(x1, y1) && insideBoard(x2, y2) && !board[x1][y1] && !board[x2][y2]) return false;
                }
            }
        }
    }
    return true;
}

void makeBoard(int curBoard) {//현재 정보로 판 구성
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            int correct = 1 << (i * 5) + j;
            int flag = correct & curBoard;
            if (flag) board[i][j] = true;
            else board[i][j] = false;
        }
    }
}

int game(int curBoard) {
    makeBoard(curBoard);//그때 그때 판 재구성
    if (isLose()) return -1;//지금 놓을 수 없다면 전사람이 승리
    char& ret = cache[curBoard];
    if (ret != -2) return ret;

    ret = -1;//내가 승리한 경우가 없다면 패배
    for (int i = 0; i < 25; i++) {
        if (((1 << i) & curBoard) == 0) {//현재 칸이 비어있고
            int j = i / 5;
            int k = i % 5;
            if (!board[j][k]) {
                for (int l = 0; l < 2; l++) {//두개짜리 블록을 놓을 수 있는 경우에 대해서
                    int x = j + twoBlock[l][0];
                    int y = k + twoBlock[l][1];
                    if (insideBoard(x, y) && !board[x][y]) {
                        int add = (1 << i) + (1 << ((x * 5) + y));
                        if(-game(curBoard + add) == 1) return ret = 1;//한번이라도 승리가 가능하면 승리
                    }
                }
                for (int l = 0; l < 3; l++) {//세개짜리 블록을 놓을 수 있는 경우에 대해서
                    int x1 = j + threeBlock[l][0][0];
                    int y1 = k + threeBlock[l][0][1];
                    int x2 = j + threeBlock[l][1][0];
                    int y2 = k + threeBlock[l][1][1];
                    if (insideBoard(x1, y1) && insideBoard(x2, y2) && !board[x1][y1] && !board[x2][y2]) {
                        int add = (1 << i) + (1 << ((x1 * 5) + y1)) + (1 << ((x2 * 5) + y2));
                        if(-game(curBoard + add) == 1) return ret = 1;//한번이라도 승리가 가능하면 승리
                    }
                }
            }
        }
    }
    return ret;//한번도 못이겼으면 패배
}

int main() {
    int tc;
    cin >> tc;
    while (tc--) {
        for (int i = 0; i < (1 << 25); i++) cache[i] = -2;
        int state = 0;
        for (int i = 0; i < 25; i++) {
            char input;
            cin >> input;
            if (input == '#') state += (1 << i);
        }
        if (game(state) == 1) cout << "WINNING" << endl;
        else cout << "LOSING" << endl;
    }
}