暴力直接解异或方程组,O(n^6)无法接受,那么我们考虑把格子分块,横着和竖着分别分为互不影响的块,这样因为障碍物最多不超过200个,那么块的个数最多为2*(800+200)=2000个,最后用bitset优化即可。

 #include <bits/stdc++.h>

 using namespace std;

 int n,cnt,Pos[],Right[],Left[];
int Crs[][],Dwn[][],MID;
char str[][]; bitset<>eq[]; void Gauss()
{
int i,j;
for(i=;i<=cnt;++i)
{
j=i;
while(!eq[j][i] && j<=cnt)j++;
if(j==cnt+)continue;
if(j!=i)swap(eq[j],eq[i]);
for(j=;j<=cnt;++j)
if(j!=i && eq[j][i])eq[j]^=eq[i];
}
return ;
} int main()
{
int i,j,temp; scanf("%d",&n); for(i=;i<=n;++i)
scanf("%s",str[i]+); for(i=;i<=n;++i)
str[][i]=str[i][]=str[i][n+]=str[n+][i]='X'; cnt=; for(j=;j<=n;++j) for(i=;i<=n+;++i)
{
if(str[i][j]!='X')Crs[i][j]=cnt;
if(str[i-][j]=='X' && str[i][j]!='X')Left[cnt]=i,Pos[cnt]=j;
if(str[i+][j]=='X' && str[i][j]!='X')Right[cnt]=i,cnt++;
} MID=cnt-; for(i=;i<=n;++i) for(j=;j<=n+;++j)
{
if(str[i][j]!='X')Dwn[i][j]=cnt;
if(str[i][j-]=='X' && str[i][j]!='X')Left[cnt]=j,Pos[cnt]=i;
if(str[i][j+]=='X' && str[i][j]!='X')Right[cnt]=j,cnt++;
} cnt--; for(i=;i<=MID;++i)
{
temp=;
eq[i].set(i); for(j=Left[i];j<=Right[i];++j)
{
eq[i][Crs[j][Pos[i]]]=eq[i][Crs[j][Pos[i]]]^;
eq[i][Dwn[j][Pos[i]]]=eq[i][Dwn[j][Pos[i]]]^;
temp^=(str[j][Pos[i]]=='X'?:str[j][Pos[i]]-);
temp^=;
} eq[i][cnt+]=temp;
#ifdef Debug
cerr << eq[i] << endl;
#endif
} for(i=MID+;i<=cnt;++i)
{
temp=;
eq[i].set(i); for(j=Left[i];j<=Right[i];++j)
{
eq[i][Crs[Pos[i]][j]]=eq[i][Crs[Pos[i]][j]]^;
eq[i][Dwn[Pos[i]][j]]=eq[i][Dwn[Pos[i]][j]]^;
temp^=(str[Pos[i]][j]=='X'?:str[Pos[i]][j]-);
temp^=;
} eq[i][cnt+]=temp;
#ifdef Debug
cerr << eq[i] << endl;
#endif
} Gauss(); #ifdef Debug
cerr << endl;
for(i=;i<=cnt;++i)
cerr << eq[i] << endl;
cerr << endl;
#endif for(i=;i<=n;++i)
{
for(j=;j<=n;++j)
{
printf("%d",str[i][j]=='X'?:(^eq[Crs[i][j]][cnt+]^eq[Dwn[i][j]][cnt+]
^(str[i][j]-)));
}
printf("\n");
} return ;
}

最新文章

  1. linux查看是什么操作系统是什么命令
  2. alphaBlend
  3. SVN安装配置和使用教程
  4. sql 流水号
  5. js_sl 延迟菜单
  6. OC: Block回调的使用demo
  7. 判断Featureclass的类型
  8. 飞行器的Pitch Yaw Roll概念图解
  9. 嵌入式Linux启动过程中的问题积累
  10. The Class Loader Hierarchy--转载
  11. hdu1166树状数组
  12. NgRx/Store 4 + Angular 5使用教程
  13. Spring Security 入门(1-2)Spring Security - 从 配置例子例子 开始我们的学习历程
  14. Activity、Fragment、Dialog基类简单整理
  15. Solrcloud(Solr集群)
  16. Rose 2003使用的问题
  17. thinkphp 3.2.1 URL 大小写问题 下面有具体说明
  18. 【转】七牛免费SSL证书,配置自定义域名CDN加速
  19. adb shell命令行
  20. 用css写出下拉框(代码转自wq群)

热门文章

  1. Istio 1.1部署实践
  2. 解决UTF-8方法归纳
  3. bzoj1877 晨跑(费用流)
  4. BZOJ 2001 线段树+LCT (TLE)
  5. android:scaleType 布局文件加载图片时候的显示方式
  6. 2CSS层叠规则(即引入CSS的三种不同方式的优先级)
  7. JVM 内存区域划分
  8. CNN结构:图片风格分类效果已成(StyleAI)
  9. WPF中的两个绑定场景
  10. (转)分布式文件存储FastDFS(六)FastDFS多节点配置