codeforces B. Fox and Cross 解题报告

题目链接：http://codeforces.com/problemset/problem/389/B

题目意思：给出一个由n行n列组成的board，其中'#'表示的一片地方恰好能画满十字架，画满的意思表示：这些十字架不能够共用'#' ！当然如果全部都是'.'，表示不画十字架。问如果有'#'和'.'的board上，是否恰好能填满所有'#'。能就输出 'YES'，否则输入'NO'

比赛的时候完全没有思路，这是赛后做出来的，参考了别人的思路。

可以这样想，考虑到十字架这么特殊的图案，以每个十字架的最高点为判断的起始点，也就是说，当能画一个十字架时，绝对是首先遇上它的最高点的！然后判断该点的正下方连续两点，还有下方第一个点紧挨着左右两边是否也为'#'即可。另外一个要考虑的地方是肯定不能画十字架的情况，每一列的第一个和最后一个字符如果为'#'是不能画十字架的，还有，倒数后两行出现'#'也是不行的。

这次比赛的题目总的来说，很有意思，虽然食蛋了！大悲剧～～～

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 char cell[maxn][maxn];

 int main()

 {

     int i, j, n, flag;

     while (scanf("%d", &n) != EOF)

     {

         for (i = ; i < n; i++)

             scanf("%s", cell[i]);

         flag = ;

         for (i = ; i < n && !flag; i++)

         {

             for (j = ; j < n && !flag; j++)

             {

                 if (cell[i][j] == '#')

                 {

                     if (j ==  || j == n- || i >= n-  || cell[i+][j] != '#' || cell[i+][j-] != '#' || cell[i+][j+] != '#' || cell[i+][j] != '#')  // 第1列，最后1列，倒数后两行，还有十字架所占的所有地方都要检测

                     {

                         printf("NO\n");

                         flag = ;

                     }

                     else   // 十字架所占的'#'注销掉，以避免阻碍判断下一个十字架

                     {

                          cell[i+][j] = '.';

                          cell[i+][j-] = '.';

                          cell[i+][j+] = '.';

                          cell[i+][j] = '.';

                     }

                 }

             }

         }

         if (!flag)

             printf("YES\n");

     }

     return ;

 }

巴特西

codeforces B. Fox and Cross 解题报告

最新文章

热门文章