博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Google Code Jam 2010 Round 1A Problem A. Rotate
阅读量:5840 次
发布时间:2019-06-18

本文共 7331 字,大约阅读时间需要 24 分钟。

 
 

Problem

In the exciting game of Join-K, red and blue pieces are dropped into an N-by-N table. The table stands up vertically so that pieces drop down to the bottom-most empty slots in their column. For example, consider the following two configurations:

- Legal Position -          .......          .......          .......          ....R..          ...RB..          ..BRB..          .RBBR..
- Illegal Position -          .......          .......          .......          .......   Bad -> ..BR...          ...R...          .RBBR..

In these pictures, each '.' represents an empty slot, each 'R' represents a slot filled with a red piece, and each 'B' represents a slot filled with a blue piece. The left configuration is legal, but the right one is not. This is because one of the pieces in the third column (marked with the arrow) has not fallen down to the empty slot below it.

A player wins if they can place at least K pieces of their color in a row, either horizontally, vertically, or diagonally. The four possible orientations are shown below:

- Four in a row -     R   RRRR    R   R     R          R     R     R         R       R     R        R         R
 
In the "Legal Position" diagram at the beginning of the problem statement, both players had lined up two pieces in a row, but not three.

 

As it turns out, you are right now playing a very exciting game of Join-K, and you have a tricky plan to ensure victory! When your opponent is not looking, you are going to rotate the board 90 degrees clockwise onto its side. Gravity will then cause the pieces to fall down into a new position as shown below:

- Start -     .......     .......     .......     ...R...     ...RB..     ..BRB..     .RBBR..
- Rotate -     .......     R......     BB.....     BRRR...     RBB....     .......     .......
- Gravity -     .......     .......     .......     R......     BB.....     BRR....     RBBR...
Unfortunately, you only have time to rotate once before your opponent will notice.

 

All that remains is picking the right time to make your move. Given a board position, you should determine which player (or players!) will have K pieces in a row after you rotate the board clockwise and gravity takes effect in the new direction.

Notes

  • You can rotate the board only once.
  • Assume that gravity only takes effect after the board has been rotated completely.
  • Only check for winners after gravity has finished taking effect.

Input

The first line of the input gives the number of test cases, TT test cases follow, each beginning with a line containing the integers N and K. The next N lines will each be exactly N characters long, showing the initial position of the board, using the same format as the diagrams above.

The initial position in each test case will be a legal position that can occur during a game of Join-K. In particular, neither player will have already formed K pieces in a row.

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1), and y is one of "Red", "Blue", "Neither", or "Both". Here, y indicates which player or players will have K pieces in a row after you rotate the board.

Limits

1 ≤ T ≤ 100.

3 ≤ K ≤ N.

Small dataset

3 ≤ N ≤ 7.

Large dataset

3 ≤ N ≤ 50.

Sample

Input 
 
Output 
 
4
7 3
.......
.......
.......
...R...
...BB..
..BRB..
.RRBR..
6 4
......
......
.R...R
.R..BB
.R.RBR
RB.BBB
4 4
R...
BR..
BR..
BR..
3 3
B..
RB.
RB.
Case #1: Neither
Case #2: Both
Case #3: Red
Case #4: Blue
 

Solution

int N = 0;int K = 0;char *inp = NULL;char *inp_cpy = NULL;int curr_row_cnt = 0;bool rd(int r, int c, int ro, int co, char chr) {        if (r >= N || r < 0 || c >= N || c < 0) return false;        if (inp_cpy[r * N + c] == chr) {        curr_row_cnt++;                if (curr_row_cnt >= K) return true;    } else {        return false;    }        return rd(r + ro, c + co, ro, co, chr);}char *solve(){        // Rotate    if (inp_cpy) free(inp_cpy);    inp_cpy = (char *)malloc(sizeof(char) * N * N);        for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            inp_cpy[N * i + j] = inp[N * (N - j - 1) + i];        }    }        // G    for (int i = N - 1; i >= 0; i--) {        for (int j = 0; j < N; j++) {            if (inp_cpy[N * i + j] != '.') {                // Can drop                int vp = i + 1;                while (1) {                    if (vp < N) {                        if (inp_cpy[N * vp + j] == '.') {                            vp++;                            continue;                        }                    }                    inp_cpy[N * (vp - 1) + j] = inp_cpy[N * i + j];                    if (vp - 1 != i) inp_cpy[N * i + j] = '.';                    break;                }            }        }    }        // Determine    bool R = false;    bool B = false;        for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            if (inp_cpy[N * i + j] == 'R') {                curr_row_cnt = 0; if (!R) R = rd(i, j, -1, -1, 'R');                curr_row_cnt = 0; if (!R) R = rd(i, j, -1,  0, 'R');                curr_row_cnt = 0; if (!R) R = rd(i, j, -1,  1, 'R');                                curr_row_cnt = 0; if (!R) R = rd(i, j,  0, -1, 'R');                curr_row_cnt = 0; if (!R) R = rd(i, j,  0,  1, 'R');                                curr_row_cnt = 0; if (!R) R = rd(i, j,  1, -1, 'R');                curr_row_cnt = 0; if (!R) R = rd(i, j,  1,  0, 'R');                curr_row_cnt = 0; if (!R) R = rd(i, j,  1,  1, 'R');                            } else if (inp_cpy[N * i + j] == 'B') {                curr_row_cnt = 0; if (!B) B = rd(i, j, -1, -1, 'B');                curr_row_cnt = 0; if (!B) B = rd(i, j, -1,  0, 'B');                curr_row_cnt = 0; if (!B) B = rd(i, j, -1,  1, 'B');                                curr_row_cnt = 0; if (!B) B = rd(i, j,  0, -1, 'B');                curr_row_cnt = 0; if (!B) B = rd(i, j,  0,  1, 'B');                                curr_row_cnt = 0; if (!B) B = rd(i, j,  1, -1, 'B');                curr_row_cnt = 0; if (!B) B = rd(i, j,  1,  0, 'B');                curr_row_cnt = 0; if (!B) B = rd(i, j,  1,  1, 'B');            }                        if (R && B)                return "Both";            }    }        if (R && !B) {        return "Red";    } else if(B && !R) {        return "Blue";    } else {        return "Neither";    }}int main(){    freopen("in.in", "r", stdin);    if (WRITE_OUT_FILE)        freopen("out.out", "w", stdout);        int T;    scanf("%d\n", &T);    if (!T) {        cerr << "Check input!" << endl;        exit(0);    }        for (int t = 1; t <= T; t++) {        if (WRITE_OUT_FILE)            cerr << "Solving: #" << t << " / " << T << endl;                scanf("%d %d\n", &N, &K);                if (inp) free(inp);        inp = (char *)malloc(sizeof(char) * N * N);        memset(inp, 0, sizeof(char) * N * N);                for (int i = 0; i < N; i++) {            for (int j = 0; j < N; j++) {                char tmp;                scanf("%c", &tmp);                inp[i * N + j] = tmp;            }            getchar();        }                auto result = solve();                printf("Case #%d: %s\n", t, result);    }        fclose(stdin);    if (WRITE_OUT_FILE)        fclose(stdout);        return 0;}

 

转载于:https://www.cnblogs.com/fatlyz/p/3689192.html

你可能感兴趣的文章
【PMP】Head First PMP 学习笔记 第一章 引言
查看>>
抓住云机遇编排工作 搞定复杂IT工作流
查看>>
MYSQL的longtext字段能放多少数据?
查看>>
MTK 平台上如何给 camera 添加一种 preview size
查看>>
云计算最大难处
查看>>
关于数据分析思路的4点心得
查看>>
mysql定时备份自动上传
查看>>
17岁时少年决定把海洋洗干净,现在21岁的他做到了
查看>>
《写给大忙人看的java se 8》笔记
查看>>
倒计时:计算时间差
查看>>
Linux/windows P2V VMWare ESXi
查看>>
Windows XP倒计时到底意味着什么?
查看>>
运维工程师在干什么学些什么?【致菜鸟】
查看>>
Linux中iptables详解
查看>>
java中回调函数以及关于包装类的Demo
查看>>
maven异常:missing artifact jdk.tools:jar:1.6
查看>>
终端安全求生指南(五)-——日志管理
查看>>
Nginx 使用 openssl 的自签名证书
查看>>
创业维艰、守成不易
查看>>
PHP环境安装套件:快速安装LAMP环境
查看>>