AI 챌린지 소스코드

 

#include <string>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <math.h>
 
using namespace std;
 
struct AI
{
    int n, m;    // map size (row, column)
    int T;        // total turns
    int x, y;    // my position
    int destRow, destCol, destScore;
    int turnCount = 0;
    int searchDistDeep;
    int searchDeep;
    int searchDir;
    bool searchFinish;
    bool searchDistFinish;
    vector<int> pass;
    int passPos;
    int countdown = 0;
    bool timeToConquer;
    int stayCount;
    int passScore;
    int distDestRow;
    int distDestCol;
    vector<int> scoreVector;
    vector<int> scoreSpotVec;
    vector<int> distVec;
    vector<int> distSpotVec;
 
    vector<int> aSpot;
    vector<vector<bool> > aClose;
    vector<vector<int> > aParent;
    vector<vector<int> > fScore;
    vector<vector< int> > gScore;
    vector<vector< int> > hScore;
    vector<int> arrayFVec;
 
    vector<vector<int> > scanDistVec;
 
    bool isFightMode = true;
 
    void init(int n, int m, int turns,
        int myRow, int myCol)
    {
        // recommended way to initialize random
        srand(clock());
 
        this->n = n;
        this->m = m;
        this->T = turns;
 
        this->x = myRow;
        this->y = myCol;
 
        searchDeep = 0;
        searchFinish = false;
        searchDistFinish = false;
        passPos = 0;
        pass.clear();
 
        destRow = x;
        destCol = y;
        destScore = -8374;
 
        timeToConquer = false;
        stayCount = 0;
 
        distDestRow = x;
        distDestCol = y;
        searchDistDeep = 0;
        turnCount = 0;
    }
 
    void scanDistance(int row, int col, vector<string> tiles) { //내위치에서 모든 진영까지의 거리 구하기
        gScore.clear();
        aSpot.clear();
        aClose.clear();
        aParent.clear();
        scanDistVec.clear();
        arrayFVec.clear();
        for (int i = 0; i < n; i++) {
            vector<int> tempGScore;
            vector<int> tempParent;
            vector<bool> tempClose;
            vector<int> tempDist;
            for (int j = 0; j < m; j++) {
                tempGScore.push_back(0);
                tempParent.push_back(-1);
                tempClose.push_back(false);
                tempDist.push_back(0);
            }
            gScore.push_back(tempGScore);
            aClose.push_back(tempClose);
            aParent.push_back(tempParent);
            scanDistVec.push_back(tempDist);
        }
 
        aSpot.push_back(row*m + col);
        arrayFVec.push_back(gScore[row][col]);
        while (aSpot.empty() == false) {
            int minFScore = 999999;
            int minFSpot = 0;
            for (int i = 0; i < arrayFVec.size(); i++) {
                if (minFScore > arrayFVec[i]) {
                    minFScore = arrayFVec[i];
                    minFSpot = i;
                }
            }
            {
                int temp = aSpot[aSpot.size() - 1];
                aSpot[aSpot.size() - 1] = aSpot[minFSpot];
                aSpot[minFSpot] = temp;
 
                temp = arrayFVec[arrayFVec.size() - 1];
                arrayFVec[arrayFVec.size() - 1] = arrayFVec[minFSpot];
                arrayFVec[minFSpot] = temp;
            }
 
            int curRow = aSpot.back() / m;
            int curCol = aSpot.back() % m;
            aClose[curRow][curCol] = true;
            aSpot.pop_back();
            arrayFVec.pop_back();
 
            if (curCol != 0 && tiles[curRow][curCol - 1] != 'X' && aClose[curRow][curCol - 1] == false) {
 
                if (aParent[curRow][curCol - 1] == -1) {
                    aParent[curRow][curCol - 1] = curRow*m + curCol;
                    gScore[curRow][curCol - 1] = gScore[curRow][curCol] + 1;
                }
                else {
                    if (gScore[curRow][curCol - 1] > gScore[curRow][curCol] + 1) {
                        aParent[curRow][curCol - 1] = curRow*m + curCol;
                        gScore[curRow][curCol - 1] = gScore[curRow][curCol] + 1;
                    }
                }
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == (curRow*m + curCol - 1)) {
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {
                    aSpot.push_back(curRow*m + (curCol - 1));
                    arrayFVec.push_back(gScore[curRow][curCol - 1]);
                }
            }
            if (curCol != m - 1 && tiles[curRow][curCol + 1] != 'X' && aClose[curRow][curCol + 1] == false) {
                if (aParent[curRow][curCol + 1] == -1) {
                    aParent[curRow][curCol + 1] = curRow*m + curCol;
                    gScore[curRow][curCol + 1] = gScore[curRow][curCol] + 1;
                }
                else {
                    if (gScore[curRow][curCol + 1] > gScore[curRow][curCol] + 1) {
                        aParent[curRow][curCol + 1] = curRow*m + curCol;
                        gScore[curRow][curCol + 1] = gScore[curRow][curCol] + 1;
                    }
                }
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == (curRow*m + curCol + 1)) {
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {
                    aSpot.push_back(curRow*m + (curCol + 1));
                    arrayFVec.push_back(gScore[curRow][curCol + 1]);
                }
 
            }
            if (curRow != 0 && tiles[curRow - 1][curCol] != 'X' && aClose[curRow - 1][curCol] == false) {
                if (aParent[curRow - 1][curCol] == -1) {
                    aParent[curRow - 1][curCol] = curRow*m + curCol;
                    gScore[curRow - 1][curCol] = gScore[curRow][curCol] + 1;
                }
                else {
                    if (gScore[curRow - 1][curCol] > gScore[curRow][curCol] + 1) {
                        aParent[curRow - 1][curCol] = curRow*m + curCol;
                        gScore[curRow - 1][curCol] = gScore[curRow][curCol] + 1;
                    }
                }
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == ((curRow - 1)*m + curCol)) {
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {
                    aSpot.push_back((curRow - 1)*m + (curCol));
                    arrayFVec.push_back(gScore[curRow - 1][curCol]);
                }
            }
            if (curRow != n - 1 && tiles[curRow + 1][curCol] != 'X' && aClose[curRow + 1][curCol] == false) {
                if (aParent[curRow + 1][curCol] == -1) {
                    aParent[curRow + 1][curCol] = curRow*m + curCol;
                    gScore[curRow + 1][curCol] = gScore[curRow][curCol] + 1;
                }
                else {
                    if (gScore[curRow + 1][curCol] > gScore[curRow][curCol] + 1) {
                        aParent[curRow + 1][curCol] = curRow*m + curCol;
                        gScore[curRow + 1][curCol] = gScore[curRow][curCol] + 1;
                    }
                }
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == ((curRow + 1)*m + curCol)) {
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {
                    aSpot.push_back((curRow + 1)*m + (curCol));
                    arrayFVec.push_back(gScore[curRow + 1][curCol]);
                }
            }
 
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tiles[i][j] != 'X' && gScore[i][j] != 0) {
                    int parentRow = i;
                    int parentCol = j;
                    while (parentRow != row || parentCol != col) {
                        scanDistVec[i][j]++;
                        int parentNum = aParent[parentRow][parentCol];
                        parentRow = parentNum / m;
                        parentCol = parentNum % m;
                    }
                }
            }
        }
    }
 
    void createPass(vector<string> tiles, vector<vector<int> > scores, int opponentRow, int opponentCol) {//경로생성함수
        int maxSpotRow = x;//최고점수가 있는 행
        int maxSpotCol = y;//최고점수가 있는 열
        int maxScore = -99999;//9개진영 최고점수
        float tempMax = -9999999.0f;//거리까지계산한 최고점수
 
        scoreVector.clear(); //진영점수 벡터
        scoreSpotVec.clear(); //진영위치 벡터
        vector<int> absDistVec; //내위치에서 해당진영의 거리값 벡터
        scanDistance(x, y, tiles);
        for (int i = 0; i < n; i++) {//모든 진영
            for (int j = 0; j < m; j++) {
                if (tiles[i][j] == 'X' || scanDistVec[i][j]>T - turnCount || (scanDistVec[i][j] == 0 && (x != i || y != j)))//벽일경우 패스
                    continue;
                {//1
                    int hap = 0;// 종합점수변수
                    int afterScore = 0;
                    int beforeScore = 0;
 
                    for (int k = i - 1; k <= i + 1; k++) {//현재진영에서 9칸
                        for (int h = j - 1; h <= j + 1; h++) {
                            if (k < 0 || h < 0 || k >= n || h >= m) continue;
                            if (tiles[k][h] == 'O') {//상대진영일경우
                                if (scores[k][h] != -9)  //-9는 감소폭없음
                                    hap += ((scores[k][h] - 1) + scores[k][h]);//상대점수감소폭과 내점수 증가폭을 더함
                                else hap += -18;
                            }
                            else if (tiles[k][h] == 'M' && scores[k][h] != -9) {
                                hap--;//내진영일경우 -1
                            }
                            else if (tiles[k][h] == 'U') {
                                hap += scores[k][h];
                            }
 
                            int score = scores[k][h];
                            if (tiles[k][h] == 'M') beforeScore += scores[k][h];//가만히 있을 경우 순수 진영 점수
                            if ((tiles[k][h] == 'M' || tiles[k][h] == 'O') && scores[k][h] != -9) score--;
                            if (tiles[k][h] == 'M' || tiles[k][h] == 'O' || tiles[k][h] == 'U') afterScore += score; //정복했을경우 순수 진영 점수
                        }
                    }
 
                    int rowDist = abs(x - i);//내위치에서 해당진영행거리
                    int colDist = abs(y - j);//내위치에서 해당진영열거리
                    if ((hap > 0) || afterScore>beforeScore) {//종합점수가 0보다 클경우만 추가함
                        if (isFightMode == true) {
                            for (int k = i - 1; k <= i + 1; k++) {
                                for (int h = j - 1; h <= j + 1; h++) {
                                    if (k < 0 || h < 0 || k >= n || h >= m) continue;
                                    if (tiles[k][h] == 'O' && scores[k][h]>0) {
                                        hap += 10 - scores[k][h];//상대진영을 우선적으로 점령하기 위한 추가적인 기능
                                    }
                                }
                            }
                        }
                        scoreVector.push_back(hap);//점수벡터
                        scoreSpotVec.push_back(i*m + j);//위치벡터
                        absDistVec.push_back(rowDist + colDist);//상대거리벡터
                    }
                }
            }
        }
 
        if (scoreVector.size() > 0) {
            vector<vector<int> > vecs;//정렬을 위해 벡터에 벡터를 넣음
            vecs.push_back(absDistVec);
            vecs.push_back(scoreVector);
            vecs.push_back(scoreSpotVec);
            quickSort(0, absDistVec.size() - 1, vecs);//퀵정렬실행
            absDistVec = vecs[0];
            scoreVector = vecs[1];
            scoreSpotVec = vecs[2];
        }
 
        for (int i = 0; i < scoreVector.size(); i++) {
 
            distDestRow = scoreSpotVec[i] / m;// 현재 벡터 행
            distDestCol = scoreSpotVec[i] % m;//현재 벡터 열
 
            searchDistDeep = scanDistVec[distDestRow][distDestCol];
            if (searchDistDeep == 0 && (distDestRow != x || distDestCol != y))
                continue;
 
            float tempHap = (float)scoreVector[i] * 1000000.0f;//거리까지 고려한 점수계산
 
            float dist = (float)searchDistDeep;
            if (dist <= 3.0f)
                dist = 1.0f;
            else
                dist = sqrt(dist)*1.5f;
 
            if (dist != 0.0f)
                tempHap /= dist;//거리로 나눈다.
 
                                //cerr << "score:" << scoreVector[i] << ",spot:" << distDestRow << "," << distDestCol << ",dist:" << searchDistDeep << ",sq dist:" << dist << "\n";
            if (tempHap > tempMax) {//그 값이 지금까지의 최고점수보다 높을경우
                maxScore = scoreVector[i];//그 값을 저장
                maxSpotRow = distDestRow;
                maxSpotCol = distDestCol;
                tempMax = tempHap;
                //cerr << "maxScore:" << maxScore << ",spot:" << maxSpotRow << "," << maxSpotCol << ",dist:" << searchDistDeep <<"sq dist"<<dist<< "\n";
            }
        }
 
        destRow = maxSpotRow;//최종 최고점수 행
        destCol = maxSpotCol;//최종 최고점수 열
        destScore = maxScore;//최종 최고점수
                             //cerr<<"destRow:"<
 
        if ((destRow == x && destCol == y) && scoreVector.size() != 0)
            pass.push_back(-1);
        else
            optimizePass(x, y, tiles);
    }
 
    void optimizePass(int row, int col, vector<string> tiles) { //목적지까지 경로를 계산하는 함수 A스타알고리즘사용
        fScore.clear();
        gScore.clear();
        hScore.clear();
        aSpot.clear();
        aClose.clear();
        aParent.clear();
        arrayFVec.clear();
        pass.clear();
 
        for (int i = 0; i < n; i++) {
            vector<int> tempFScore;
            vector<int> tempGScore;
            vector<int> tempHScore;
            vector<int> tempParent;
            vector<bool> tempClose;
            for (int j = 0; j < m; j++) {
                tempGScore.push_back(0);
                tempHScore.push_back(abs(destRow - i) + abs(destCol - j));
                tempFScore.push_back(tempHScore.back());
                tempParent.push_back(-1);
                tempClose.push_back(false);
            }
            fScore.push_back(tempFScore);
            hScore.push_back(tempHScore);
            gScore.push_back(tempGScore);
            aClose.push_back(tempClose);
            aParent.push_back(tempParent);
        }
        //초기화완료
 
        {
            int tempRow = x;
            int tempCol = y;
            for (int i = 0; i < pass.size(); i++) {
                aClose[tempRow][tempCol] = false;
                int dir = pass[i];
                if (dir == 0)
                    tempRow--;
                else if (dir == 1)
                    tempCol--;
                else if (dir == 2)
                    tempRow++;
                else if (dir == 3)
                    tempCol++;
            }
            aClose[tempRow][tempCol] = false;
        }
 
 
        aSpot.push_back(row*m + col);//현재 위치를 넣고 시작
        arrayFVec.push_back(fScore[row][col]);
 
        while (aSpot.empty() == false) {
            int minFScore = 99999999;//최소점수를 초기화
            int minFSpot = 0;//최소점수 위치
            for (int i = 0; i < arrayFVec.size(); i++) {//F점수 벡터를 돌면서 가장 작은 값을 추출해냄
                if (minFScore > arrayFVec[i]) {
                    minFScore = arrayFVec[i];
                    minFSpot = i;
                }
            }
            {
                int temp = aSpot[aSpot.size() - 1];//가장 마지막 위치값과 가장 낮은점수의 값을 위치교환함
                aSpot[aSpot.size() - 1] = aSpot[minFSpot];//
                aSpot[minFSpot] = temp;
 
                temp = arrayFVec[arrayFVec.size() - 1];
                arrayFVec[arrayFVec.size() - 1] = arrayFVec[minFSpot];
                arrayFVec[minFSpot] = temp;
 
            }
 
            int curRow = aSpot.back() / m;//행값
            int curCol = aSpot.back() % m;//열값
 
            aClose[curRow][curCol] = true;//aClose는 내가 들렸으면 true로 변환->다시 못들리게
 
            aSpot.pop_back();
            arrayFVec.pop_back();
            if ((curRow == destRow && curCol == destCol)) {//만약 현재위치가 목적지에 도달한거면
                int parentRow = curRow;
                int parentCol = curCol;
                pass.clear();//경로 초기화
                while (parentRow != row || parentCol != col) {//지금 계산하고있는 위치가 시작점이 아닐때까지 반복
                    int parentNum = aParent[parentRow][parentCol];//부모의 위치를 저장
                    if (parentNum - (parentRow*m + parentCol) == 1) {//부모 위치와 계산중인 위치 차이가 1이면
                        pass.push_back(1);//왼쪽에 있다는 의미이다.
                    }
                    else if (parentNum - (parentRow*m + parentCol) == -1) {//결과가 -1이면 오른쪽에 있다는 뜻이다.
                        pass.push_back(3);
                    }
                    else if (parentNum - (parentRow*m + parentCol) == m) {//결과가 열 개수면 위에 있다는 뜻이다.
                        pass.push_back(0);
                    }
                    else if (parentNum - (parentRow*m + parentCol) == -m) {//결과가 -열개수 면 아래에 있다는 뜻이다.
                        pass.push_back(2);
                    }
                    parentRow = parentNum / m;//다음 부모의 위치를 저장
                    parentCol = parentNum % m;
                }
                return;
            }
 
            if (curCol != 0 && tiles[curRow][curCol - 1] != 'X' && aClose[curRow][curCol - 1] == false) {//현재 열이 가장 왼쪽이 아니면서 왼쪽이 X가 아니고 들렸던 곳이 아니면 실행
                if (aParent[curRow][curCol - 1] == -1) {//만약 왼쪽에 부모가 없으면
                    aParent[curRow][curCol - 1] = curRow*m + curCol;//부모 등록
                    gScore[curRow][curCol - 1] = gScore[curRow][curCol] + 1;//g스코어 등록
                }
                else {
                    if (gScore[curRow][curCol - 1] > gScore[curRow][curCol] + 1) {//이미 있던 g스코어 현재 내위치에서 +1한값보다 크면 작은걸로 대체함
                        aParent[curRow][curCol - 1] = curRow*m + curCol;
                        gScore[curRow][curCol - 1] = gScore[curRow][curCol] + 1;
                    }
                }
                fScore[curRow][curCol - 1] = (gScore[curRow][curCol - 1] + hScore[curRow][curCol - 1]);//f스코어는 g스코어와 h스코어의 합
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == (curRow*m + curCol - 1)) {//만약 현재위치가 이미 벡터안에 등록되어있으면 벡터에 넣지않고 나감
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {//만약 벡터안에 없으면 등록함
                    aSpot.push_back(curRow*m + (curCol - 1));
                    arrayFVec.push_back(fScore[curRow][curCol - 1]);
                }
            }
            if (curCol != m - 1 && tiles[curRow][curCol + 1] != 'X' && aClose[curRow][curCol + 1] == false) {
                if (aParent[curRow][curCol + 1] == -1) {
                    aParent[curRow][curCol + 1] = curRow*m + curCol;
                    gScore[curRow][curCol + 1] = gScore[curRow][curCol] + 1;
                }
                else {
                    if (gScore[curRow][curCol + 1] > gScore[curRow][curCol] + 1) {
                        aParent[curRow][curCol + 1] = curRow*m + curCol;
                        gScore[curRow][curCol + 1] = gScore[curRow][curCol] + 1;
                    }
                }
                fScore[curRow][curCol + 1] = (gScore[curRow][curCol + 1] + hScore[curRow][curCol + 1]);
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == (curRow*m + curCol + 1)) {
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {
                    aSpot.push_back(curRow*m + (curCol + 1));
                    arrayFVec.push_back(fScore[curRow][curCol + 1]);
                }
            }
            if (curRow != 0 && tiles[curRow - 1][curCol] != 'X' && aClose[curRow - 1][curCol] == false) {
                if (aParent[curRow - 1][curCol] == -1) {
                    aParent[curRow - 1][curCol] = curRow*m + curCol;
                    gScore[curRow - 1][curCol] = gScore[curRow][curCol] + 1;
                }
                else {
                    if (gScore[curRow - 1][curCol] > gScore[curRow][curCol] + 1) {
                        aParent[curRow - 1][curCol] = curRow*m + curCol;
                        gScore[curRow - 1][curCol] = gScore[curRow][curCol] + 1;
                    }
                }
                fScore[curRow - 1][curCol] = (gScore[curRow - 1][curCol] + hScore[curRow - 1][curCol]);
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == ((curRow - 1)*m + curCol)) {
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {
                    aSpot.push_back((curRow - 1)*m + (curCol));
                    arrayFVec.push_back(fScore[curRow - 1][curCol]);
                }
            }
            if (curRow != n - 1 && tiles[curRow + 1][curCol] != 'X' && aClose[curRow + 1][curCol] == false) {
                if (aParent[curRow + 1][curCol] == -1) {
                    aParent[curRow + 1][curCol] = curRow*m + curCol;
                    gScore[curRow + 1][curCol] = gScore[curRow][curCol] + 1;
                }
                else {
                    if (gScore[curRow + 1][curCol] > gScore[curRow][curCol] + 1) {
                        aParent[curRow + 1][curCol] = curRow*m + curCol;
                        gScore[curRow + 1][curCol] = gScore[curRow][curCol] + 1;
                    }
                }
                fScore[curRow + 1][curCol] = (gScore[curRow + 1][curCol] + hScore[curRow + 1][curCol]);
                bool isExist = false;
                for (int i = 0; i < aSpot.size(); i++) {
                    if (aSpot[i] == ((curRow + 1)*m + curCol)) {
                        isExist = true;
                        break;
                    }
                }
                if (isExist == false) {
                    aSpot.push_back((curRow + 1)*m + (curCol));
                    arrayFVec.push_back(fScore[curRow + 1][curCol]);
                }
            }
        }
    }
 
    string action(vector<string> tiles, vector<vector<int> > scores, int opponentRow, int opponentCol)
    {
        string act = "STAY";
 
        int afterScore = 0;//정복했을경우 순수점수
        int beforeScore = 0;//아무것도 안했을경우 순수점수
        int damageEarn = 0;//상대와나의 점수격차 
        bool isMeExist = false;//현재 위치에서 9개 진영중에 내진영이 있는지 여부검사
        for (int i = x - 1; i <= x + 1; ++i) {
            for (int j = y - 1; j <= y + 1; ++j) {
                if (i < 0 || j < 0 || i >= n || j >= m) continue;
 
                if (tiles[i][j] == 'M' && scores[i][j] != -9) {//상대점수감소까지 고려한 계산
                    damageEarn--;//내 진영일경우 현재점수에서 -1만 감소한다.
                }
                else if (tiles[i][j] == 'O') { //상대진영일 경우
                    if (scores[i][j] != -9) {
                        damageEarn += (scores[i][j] - 1) + scores[i][j]; //상대점수를 없애면서 내점수를 얻는다.
                    }
                    else {
                        damageEarn += -18; //-9는 감소폭이 없으므로 종합-18을 얻게된다.
                    }
                }
                else if (tiles[i][j] == 'U') {//중립지역이면 점수그대로 가져온다.
                    damageEarn += scores[i][j];
                }
 
                if (tiles[i][j] == 'M' && scores[i][j] != -9) { //내진영이면서 -9가 아닐경우(-9는 정복해도 감소폭이 없으므로 내진영으로 치지않는다)
                    isMeExist = true;//내 진영이 있는지 표현하는 변수
                }
                int score = scores[i][j];
                if (tiles[i][j] == 'M') beforeScore += scores[i][j];//가만히 있을 경우 순수 진영 점수
                if ((tiles[i][j] == 'M' || tiles[i][j] == 'O') && scores[i][j] != -9) score--;
                if (tiles[i][j] == 'M' || tiles[i][j] == 'O' || tiles[i][j] == 'U') afterScore += score; //정복했을경우 순수 진영 점수
            }
        }
        //
        if (isMeExist == true && (x != destRow || y != destCol)) { //내위치에서 9개 진영에 내진영이 있으면서 목적지가 아닌경우 이 지역을 먹지않는다.(감소폭이 심해서)
            beforeScore = afterScore = 0;
            damageEarn = 0;
        }
 
        int destRowDist = abs(x - destRow);//내위치와 목적지 행 거리
        int destColDist = abs(y - destCol);//내위치와 목적지 열 거리
        int destDist = destRowDist + destColDist;//종합거리
        bool isScoreExist = false;
 
        if (((damageEarn>0) || afterScore>beforeScore)) { //상대방과 상대비교를 통해 먹을 가치가 있거나 상대방과 상관없이 먹을 가치가 있으면 점령한다.
            if (destDist == 0 || (destRowDist >= 3 || destColDist >= 3)) {//목적지 거리가 내가 있는 곳이거나 행 또는 열거리가 3이상인 경우 점령한다.
                act = "CONQUER";//최종적으로 이 진영을 먹을 가치가 있다고 하면 정복한다.
            }
            else if (destRowDist < 3 && destColDist < 3) {//또는 목적지가 내위치가 아니면서 거리가 3미만일 경우
                if (destRowDist <2 && destColDist <2) {//만약 거리가 목적지 거리가 행과 열 모두 2미만일 경우
                    if ((tiles[x][y] == 'M'&&scores[x][y] != -9) || tiles[x][y] == 'O' || tiles[x][y] == 'U') {//만약 내위치가 점령된 지역이면서 -9점이 아니거나 미점령지역일경우 먹지 않는다.
                        isScoreExist = true;//
                    }
                }
                for (int kk = x - 1; kk <= x + 1; kk++) {//내 위치에서 9칸 검사
                    for (int cc = y - 1; cc <= y + 1; cc++) {
                        if (kk < 0 || cc < 0 || kk >= n || cc >= m || (x == kk && y == cc)) continue;
                        if (abs(destRow - kk) <= 1 && abs(destCol - cc) <= 1) {//만약 그 사이에 X나 *이면 상관없으므로 먹어도됨
                            if ((tiles[kk][cc] == 'M'&&scores[kk][cc] != -9) || tiles[kk][cc] == 'O' || tiles[kk][cc] == 'U') {//해당 위치가 내진영이고 -9가 아니거나 적진영이거나 미점령지면 안먹는다.
                                isScoreExist = true;
                                break;
                            }
                        }
                    }
                    if (isScoreExist == true)//안먹는다고 결정했으면 나간다.
                        break;
                }
                if (isScoreExist == false) {//모든 검사를 통과했으면 점령한다.
                    //cerr << "con2\n";
                    act = "CONQUER";
                }
            }
        }
        else
            isScoreExist = true;
 
        if (isScoreExist == true || act == "STAY") {//현재 위치를 점령하지 않는다고 할때 경로를 다시 짠다.
            createPass(tiles, scores, opponentRow, opponentCol);//경로생성
 
            if (pass.size() > 0) {//경로가 존재하면
                int dir = pass.back();//벡터에 저장된 경로에서 한개를 꺼낸다.
                pass.pop_back();
 
                if (dir == 0 && x != 0 && tiles[x - 1][y] != 'X') {//윗방향이면서 위에 길이 있고 벽이 아닌경우
                    act = "U";
                    x--;
                }
                else if (dir == 1 && y != 0 && tiles[x][y - 1] != 'X') {
                    act = "L";
                    y--;
                }
                else if (dir == 2 && x != n - 1 && tiles[x + 1][y] != 'X') {
                    act = "D";
                    x++;
                }
                else if (dir == 3 && y != m - 1 && tiles[x][y + 1] != 'X') {
                    act = "R";
                    y++;
                }
                else if (dir == -1)
                    act = "CONQUER";
            }
        }
        else if (act == "CONQUER") {//만약 점령하기로 한경우
            vector<int> compareScore;
            vector<int> compareSpot;
            int maxScore = -99999;
            int maxSpot = 0;
            for (int i = x - 1; i <= x + 1; i++) {//내 진영에서 9칸 검사
                for (int j = y - 1; j <= y + 1; j++) {
                    if (i < 0 || j < 0 || i >= n || j >= m || tiles[i][j] == 'X') continue;
                    if ((i == x - 1 && j == y - 1) || (i == x + 1 && j == y - 1) || (i == x - 1 && j == y + 1) || (i == x + 1 && j == y + 1)) continue;
                    //대각선위치에 있는 곳은 검사하지 않는다. 바로 다음에 갈수없으므로.
                    int hap = 0;
                    for (int k = i - 1; k <= i + 1; k++) {//9칸에 대해서 또 9칸을 검사한다.
                        for (int h = j - 1; h <= j + 1; h++) {
                            if (k < 0 || h < 0 || k >= n || h >= m) continue;
                            if (tiles[k][h] == 'M' && scores[k][h] != -9) {//상대점수감소까지 고려한 계산
                                hap--;//내 진영일경우 현재점수에서 -1만 감소한다.
                            }
                            else if (tiles[k][h] == 'O') { //상대진영일 경우
                                if (scores[k][h] != -9) {//점수가 -9가 아닌경우.
                                    hap += (scores[k][h] - 1) + scores[k][h]; //상대점수를 없애면서 내점수를 얻는다.
                                }
                                else {
                                    hap += -18; //-9는 감소폭이 없으므로 종합-18을 얻게된다.
                                }
                            }
                            else if (tiles[k][h] == 'U') {//중립지역이면 점수그대로 가져온다.
                                hap += scores[k][h];
                            }
                        }
                    }
                    if (hap > 0) {//합이 0보다 큰경우
                        if (isFightMode == true) {//상대진영 점령을 우선으로 한다.(마지막에 추가됨)
                            for (int k = i - 1; k <= i + 1; k++) {
                                for (int h = j - 1; h <= j + 1; h++) {
                                    if (k < 0 || h < 0 || k >= n || h >= m) continue;
                                    if (tiles[k][h] == 'O' && scores[k][h]>0) {//상대진영이면서 0보다 큰경우
                                        hap += 10 - scores[k][h];//무조건 10점을 부여한다.
                                    }
                                }
                            }
                        }
                        if (i == x && j == y) {//i,j가 내진영인 경우 ->내 위치보다 높은 점수가 있을때만 움직이기 위해.
                            maxScore = hap;//최고점수에 현재 합을 저장
                            maxSpot = i*m + j;//최고점수 위치에 i,j위치 저장
                        }
                        compareSpot.push_back(i*m + j);//비교를 위한 벡터에 위치를 넣음
                        compareScore.push_back(hap);//비교점수백터에 합 넣음
                    }
                }
            }
            if (compareSpot.size() > 0) {//벡터안에 적어도 한개가 있으면
                for (int i = 0; i < compareSpot.size(); i++) {
                    if (maxScore < compareScore[i]) {//내 위치점수보다 높은점수가 있으면
                        maxScore = compareScore[i];//최고점수를 대체함
                        maxSpot = compareSpot[i];
                    }
                }
                if (maxSpot == x*m + y || timeToConquer) {//최고점수위치가 현재위치이거나 이전에 움직여서 점령해야만 하는 상황인경우 점령함
                    act = "CONQUER";
                    timeToConquer = false;//다음턴에 점령을 확신하기 위한 변수
                }
                else {//다른 위치에 더 높은 점수가 있는경우
                    int tempRow = maxSpot / m;//최고점수위치값 저장
                    int tempCol = maxSpot % m;
                    timeToConquer = true;//다음턴에 무조건 점령한다는 확신
                    if (tempRow == x && tempCol<y) {//위치값에 따라 이동방향결정
                        act = "L";
                        y--;
                    }
                    else if (tempRow == x && tempCol>y) {
                        act = "R";
                        y++;
                    }
                    else if (tempRow > x && tempCol == y) {
                        act = "D";
                        x++;
                    }
                    else if (tempRow < x && tempCol == y) {
                        act = "U";
                        x--;
                    }
                }
            }
        }
 
 
        // deal with 'OUT OF GRID'
        if (y < 0) y = 0;
        if (x < 0) x = 0;
        if (x >= n) x = n - 1;
        if (y >= m) y = m - 1;
 
        turnCount++;//턴수저장
 
        return act;
    }
 
    int partition(int low, int high, vector<vector<int> >& vecs) { //퀵정렬
        int i, j, temp, temp2;
        int pivotItem;
        pivotItem = vecs[0][low];
        j = low;
        for (i = low + 1; i <= high; i++)
        {
            if (vecs[0][i]<pivotItem)
            {
                j++;
                for (int k = 0; k < vecs.size(); k++) {
                    temp = vecs[k][i];
                    vecs[k][i] = vecs[k][j];
                    vecs[k][j] = temp;
                }
            }
        }
 
        for (int k = 0; k < vecs.size(); k++) {
            temp = vecs[k][low];
            vecs[k][low] = vecs[k][j];
            vecs[k][j] = temp;
        }
 
        return j;
    }
 
    void quickSort(int low, int high, vector<vector<int> >& vecs)//퀵정렬 함수 여러개 바꿀 벡터를 벡터로 가져옴
    {
        int pivotPoint;
        if (high>low)
        {
            pivotPoint = partition(low, high, vecs);
            quickSort(low, pivotPoint - 1, vecs);
            quickSort(pivotPoint + 1, high, vecs);
        }
    }
};
 
 
// DO NOT TOUCH ANYTHING {{{
int main() {
    AI* instance = new AI();
    int n, m, T, x, y;
    cin >> n >> m >> T >> x >> y;
 
    instance->init(n, m, T, x, y);
 
    cout << "READY" << endl;
    for (int turn = 1; turn <= T; ++turn) {
        vector<string> S1;
        for (int i = 0; i< n; ++i) {
            string buf;
            cin >> buf;
            S1.push_back(buf);
        }
        vector< vector<int> > S2;
        for (int i = 0; i < n; ++i) {
            S2.push_back(vector<int>(m));
            for (int j = 0; j < m; ++j) {
                cin >> (S2.back()[j]);
            }
        }
        int ox, oy;
        cin >> ox >> oy;
        string act = instance->action(S1, S2, ox, oy);
        cout << act.c_str() << endl;
    }
    delete instance;
    return 0;
}
// END OF DO NOT TOUCH ANYTHING }}}