時間限制?5000 ms?內(nèi)存限制?65536 KB

題目描述

?? ?In a parallel universe, Saber has won the champion of every kind of board games. She even defeated the AI program BetaGo recently! After all the victory she has got, Saber found life so boring that she decided to develop her own kind of board game. The new game named "Diamond Wars" involves two players to play on a randomly generated?N?M?board, each grid is filled with red or blue, indicating the first and the second players. The players then decide?an integer?K?by random. Next, each player take turns to fill a part of the board following the rules: one must choose a grid?(x,y)?in?his color,?K≤x≤N?K+1?and?K≤y≤M?K+1, and if for all the grids?(i,j)? ? ? that satisfy?∣i?x∣+∣j?y∣≤K?1? ? ? ? ? ? ? ? ?, they are all of the player's color, he will color them to green and get 1 score. We?call this?(x,y)?a valid grid. If one player chose an invalid?(x,y), that grid as well as all grids?(i,j)? ? ? ?satisfing the formula will become the opponent's color! The first one who is unable to move when there are still non-green grids on the board, or the one with less score at last will lose the game. As an expert in board games, Saber wants to know exactly how many valid grids the first player can choose at the very beginning. She is confident that she will win every game even being the second player to move.?

輸入格式

?? ?The input starts with an integer?T?(1≤T≤20), ? ? ?indicating the number of test cases.?
?? ?For each test case, the first line contains three integers?N,M,K?(1≤N,M≤100,1≤2?K≤min(N+1,M+1)). The following?N?lines contain the board, each line with exactly?M?characters. We assume red be 'O' and blue be 'X' to simplify the problem.

輸出格式

?? ?For each test case, print a line containing the answer to the problem Saber is interested in.

【本文出自http://blog.csdn.net/u012662688/article/details/51163528，轉(zhuǎn)載請注明】

輸入樣例

1 4 5 2 XOOOO OOOOX OOOOO OXXOO

輸出樣例

3 一個好好想一想，大家都能過的題，先枚舉出所有符合條件的x、y，再枚舉出所有符合條件的i、j即可。4重for循環(huán)。

#include<cstdio> #include<cmath> #include<algorithm> #define N 150 using namespace std; int main(){int t,n,i,m,k;char str[N][N];for(scanf("%d",&t);t--;){scanf("%d%d%d",&n,&m,&k);for(i=1;i<=n;i++)scanf("%s",str[i]+1);int x,y;int ans=0;int sig;int px,py;for(x=k;x<=n-k+1;x++){for(y=k;y<=m-k+1;y++){sig=1;if(str[x][y]=='O'){for(px=1;px<=n&&sig;px++){for(py=1;py<=m&&sig;py++){if(abs(px-x)+abs(py-y)<=k-1){if(str[px][py]!='O')sig=0;}}}if(sig){ans++;}}}}printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的北邮OJ 1022. 16校赛-Saber's Board的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。