逆向暴力求解 538.D Weird Chess

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = 1e3;

 char mp[maxn][maxn];

 char outmp[maxn][maxn];

 int vis[maxn][maxn];

 struct node{

     int x,y;

 }sp[maxn*];

 int cnt;

 void init()

 {

     memset(vis,,sizeof(vis));

     cnt = ;

 }

 int n;

 bool check(int dx,int dy)

 {

     int flag = ;

     //int broke = 0;

     for(int i = ;i < cnt;++i)

     {

         int nowx = sp[i].x;

         int nowy = sp[i].y;

         int nx = nowx + dx;

         int ny = nowy + dy;

         if(nx <  || nx>= n || ny <  || ny >= n)continue;

         if(mp[nx][ny] == '.')

         {

             return false;

         }

     }

     for(int i = ;i < cnt;++i)

     {

         int nowx = sp[i].x;

         int nowy = sp[i].y;

         int nx = nowx + dx;

         int ny = nowy + dy;

         if(nx <  || nx>= n || ny <  || ny >= n)continue;

         if(mp[nx][ny] == 'x')

         {

             vis[nx][ny]++;

         }

     }

     return true;

 }

 int main()

 {

     scanf("%d",&n);

     init();

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

     {

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

         for(int j = ;j < n;++j)

         {

             if(mp[i][j] == 'o')

             {

                 sp[cnt].x = i;

                 sp[cnt++].y = j;

             }

         }

     }

     int len =  * n - ;

     int midx = n - ,midy = n - ;

     outmp[midx][midy] = 'o';

     for(int i = ;i < len;++i)

     {

         for(int j = ;j < len;++j)

         {

             if(i == midx && j == midy)continue;

             int dx = i - midx;

             int dy = j - midy;

             if(check(dx,dy))

                 outmp[i][j] = 'x';

             else

                 outmp[i][j] = '.';

         }

     }

     int flag = ;

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

     {

         for(int j = ;j < n;++j)

         {

             if(mp[i][j] == 'x' && vis[i][j] == )

             {

                 flag = ;

             }

         }

     }

     if(flag)

     {

         printf("YES\n");

         for(int i = ;i < len;++i)

         {

             printf("%s\n",outmp[i]);

         }

     }

     else

         printf("NO\n");

     return ;

 }

11.12.2018

逆向暴力求解 538.D Weird Chess

New Point：

没有读好题

越界的情况无法判断，所以输出任何一种就可以

所以他给你的样例输出完全是误导

输出还搞错了~

输出的举证中间竟然空格隔开每一个字符，真的是不该错，否则应该是1A吧

然后空间开小了，地图空间倒是注意到了，但是你存取’o’的空间只有1000，而地图大小最大是50*50所以最多是2500个’o’的地址

中间的选择代码逻辑有些混乱

要加强练习！

Describe:

定义新的下棋游戏，给你多个棋子’o’和多个走向’x’，如果走向’x’和’o’重合显示’o’,问你能不能求出一个棋子的走动规则，并用2n-1 * 2n-1的图像表示出来

Solution:

我的思路：扫数据的时候记录好多个棋子的位置，然后遍历输出的数组，记录dx，dy，再对应到输入的图中去判断是否可行，可行就标记’x’不可行就标记’.’，略过中间点’o’，；

对于没有解决方案的情况：没有读好题

·原图中每个’x’必须且只能被访问一次

·原图中源点可以被访问多次不受限制

·图中’.’不能被访问

所以遍历输出数组后判断’x’对应的vis数组访问情况

11.13补充

判断可行

就是先扫一遍只要到达的点不是’.’就可行，越界也没问题

判断不可行

原图中若有’x’没有被轰炸过则方案不可行

认真读题

50