NOIP|P2346 四子连棋 - 迭代加深 NOIP|暴力

【NOIP|P2346 四子连棋 - 迭代加深】难点是想到颜色可以为O，搜索的过程中可能会把一个O移动到另一个O上面，然后搜索的颜色参数就变成O就错了。。。
也没什么好办法，就是判到O直接跳过。。。
另外，要习惯把各种量写在参数表里，这样能省很多代码。。。也更好调试

#include #include #include #include #include #include #include using namespace std; #define debug(x) cerr << #x << "=" << x << endl; const int MAXN = 200000 + 10; typedef long long ll; char gra[10][10]; int ans,deg,x1,y1,x2,y2; bool flg; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; bool check() { for(int i=1; i<=4; i++) { if(gra[i][1] == gra[i][2] && gra[i][2] == gra[i][3] && gra[i][3] == gra[i][4]) return true; } for(int j=1; j<=4; j++) { if(gra[1][j] == gra[2][j] && gra[2][j] == gra[3][j] && gra[3][j] == gra[4][j]) return true; } if(gra[1][1] == gra[2][2] && gra[2][2] == gra[3][3] && gra[3][3] == gra[4][4]) return true; if(gra[1][4] == gra[2][3] && gra[2][3] == gra[3][2] && gra[3][2] == gra[4][1]) return true; return false; } bool id_dfs(int x, int deg, int x1, int y1, int x2, int y2, char col) { if(x == deg + 1) { if(check()) return true; else return false; } for(int i=0; i<=3; i++) { int nx1 = x1 + dx[i]; int ny1 = y1 + dy[i]; int nx2 = x2 + dx[i]; int ny2 = y2 + dy[i]; if(nx1 >= 1 && nx1 <= 4 && ny1 >= 1 && ny1 <= 4 && gra[nx1][ny1] != col && gra[nx1][ny1] != 'O') { swap(gra[x1][y1], gra[nx1][ny1]); if(id_dfs(x+1, deg, nx1, ny1, x2, y2, gra[x1][y1])) return true; swap(gra[x1][y1], gra[nx1][ny1]); } if(nx2 >= 1 && nx2 <= 4 && ny2 >= 1 && ny2 <= 4 && gra[nx2][ny2] != col && gra[nx2][ny2] != 'O') { swap(gra[x2][y2], gra[nx2][ny2]); if(id_dfs(x+1, deg, x1, y1, nx2, ny2, gra[x2][y2])) return true; swap(gra[x2][y2], gra[nx2][ny2]); } } return false; } int main() { for(int i=1; i<=4; i++) { for(int j=1; j<=4; j++) { cin >> gra[i][j]; if(gra[i][j] == 'O') { if(x1 == 0) { x1 = i, y1 = j; } else { x2 = i, y2 = j; } } } } while(1) { ++deg; if(id_dfs(1, deg, x1, y1, x2, y2, 0)) { printf("%d", deg); break; } } return 0; }

NOIP|P2346 四子连棋 - 迭代加深

推荐阅读

色母片是什么

mysql怎么查找递归 sql实现mysql递归查询

java数组基础详解

宝宝|婴幼儿意外伤害第一时间如何正确处置？

mysql服务层中解析器包含哪些功能 mysql解析器是什么

别出心裁的“烧南北”

真机|小米又站起来了！MIX 4真机屏幕曝光：这效果太好

水果拼盘常用水果三种水果拼盘图片

品质分析方法,统计学分析方法有哪些

2023年北京郁金香文化节有几个展区参加 2023年北京郁金香文化节有几个展区

拍摄延时摄影用什么格式，延时摄影的图片格式

htcG13手机应该下个什么文件阅读器或者浏览器？一打开爱奇艺就自动把视频图片查看器音乐播放器全改成了爱奇艺万能播放器，

轻轨是地铁吗

mysql解压tar

百度导航下载导航，百度地图导航下载

go语言控制台输出 go语言控制台输入

预算在1500,如何配置一台玩DNF的电脑？

破晓色是什么颜色？

工程竣工验收需要哪些资料？工程竣工验收需要哪些资料

比亚迪s7报价多少比亚迪s7报价多少?