一流的手机网站建设,在线培训系统app,网站建设视频代码,佛山网站建设哪家公司好样例1输入#xff1a;
3 3
10 1 52
20 30 1
1 2 3
样例1输出#xff1a;
3
样例2输入#xff1a;
4 3
1 1 1 1
1 30 80 2
1 1 1 100
样例2输出#xff1a;
10
分析#xff1a;这道题目我们直接从(1,1)点开始进行dfs搜索即可#xff0c;但是需要注意一点的是我们搜… 样例1输入
3 3
10 1 52
20 30 1
1 2 3
样例1输出
3
样例2输入
4 3
1 1 1 1
1 30 80 2
1 1 1 100
样例2输出
10
分析这道题目我们直接从(1,1)点开始进行dfs搜索即可但是需要注意一点的是我们搜索的时候并不是沿着一条路径进行搜索而是从当前已经走过的所有点中选出一个点然后沿着不同方向去搜索这样我们就可以搜出所有的连通块每次搜出一个连通块时还需要检测剩余的部分是否是一个连通块那么检测剩余部分是否是一个连通块我们可以用并查集来实现。这样大体的步骤就实现了接下来就是剪枝了为了防止同样的状态被多次搜索我们可以用哈希优化一下随意设置一个哈希函数然后求出每个连通块对应的哈希值然后进行去重即可还有可以优化的一点就是我们每次尽可能选取值大的点进行搜索这样得到目标值的连通块内的点就会尽可能小。
需要说明的一点就是由于蓝桥原题是没有明确说明两部分都必须连通的所以也就没必要加上判断连通的那部分而且他数据中都是一笔画形成的连通块没有考虑周全所以本代码在这两方面进行了优化但会在洛谷上提交时会有一个点超时那是因为本代码充分考虑到其余部分是否连通以及连通块形状任意这两个问题。
细节见代码
#includecstdio
#includeiostream
#includealgorithm
#includecstring
#includemap
#includequeue
#includevector
#includecmath
#includeunordered_set
using namespace std;
typedef pairint,int PII;
const int N12;
const int P13331;//P用于哈希
unordered_setunsigned long longst;
PII p[N*N];//存放当前已选的点
int a[N][N];
bool vis[N][N];
int fu[N*N],sum,ans,n,m;
int dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};
bool cmp(PII x,PII y)
{return a[x.first][x.second]a[y.first][y.second];
}
int find(int x)
{if(fu[x]!x) return fu[x]find(fu[x]);return x;
}
bool check_connect(int cnt)//检查剩余的n*m-cnt个点是否连通
{for(int i1;in*m;i) fu[i]i;int tn*m-cnt;for(int i1;in;i)for(int j1;jm;j)if(!vis[i][j]){for(int k0;k4;k){int nxidx[k],nyjdy[k];if(nx1||nxn||ny1||nym) continue;if(vis[nx][ny]) continue;int fxfind((i-1)*mj),fyfind((nx-1)*mny);if(fxfy) continue;t--;fu[fx]fy;}}return t1;
}
bool check_exit()//检查当前连通块是否已经被搜索过是的话返回true否则返回false
{unsigned long long t0; for(int i1;in;i)for(int j1;jm;j)if(vis[i][j])tt*Pi*(P-3)j*(P102);if(st.count(t)) return true;//哈希去重st.insert(t);return false;
}
void dfs(int s,int cnt)//s和cnt分别代表当前已经选出来的数的和及个数
{if(ssum/2){if(check_connect(cnt)) ansmin(ans,cnt);//检查其他格子是否为一个连通块 return ;}if(ssum/2||cntans) return ;//剪枝 PII next[N*N];//存放下一次搜索的点 int t0;for(int i1;icnt;i){int nowxp[i].first,nowyp[i].second;for(int j0;j4;j){int nxnowxdx[j],nynowydy[j];if(nx1||nxn||ny1||nym) continue;if(vis[nx][ny]) continue;next[t]{nx,ny};}}sort(next1,nextt1,cmp);for(int i1;it;i){if(next[i]next[i-1]) continue;p[cnt1]next[i];vis[next[i].first][next[i].second]true;if(!check_exit())//检查当前连通块是否已经被搜索过dfs(sa[next[i].first][next[i].second],cnt1);vis[next[i].first][next[i].second]false;}
}int main()
{cinmn;for(int i1;in;i)for(int j1;jm;j){scanf(%d,a[i][j]);suma[i][j];}if(sum1){printf(0);return 0;}ans0x3f3f3f3f;vis[1][1]true;p[1]{1,1};dfs(a[1][1],1);if(ans0x3f3f3f3f) ans0;printf(%d,ans);return 0;
}
