- chenshixian 的博客
陈室先的总结7.25day14
-
chenshixian
LV 2
@
2024-7-26 17:12:08
题目传送门
T1小W的数独
没写
思路
当遇到星号时，可以枚举里面可以填的数，再判断可不可以填，最后当所有星号都填完时，数量++
代码
#include<bits/stdc++.h>
using namespace std;
char a[10][10];
struct P{
int x,y;
}xh[100];
int idx,n,cn;
bool gg(int x,int y,char s){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==x&&a[i][j]==s)return 0;
if(j==y&&a[i][j]==s)return 0;
if(x+y==i+j&&a[i][j]==s)return 0;
if(x-y+n==i-j+n&&a[i][j]==s)return 0;
}
}
return 1;
}
void dfs(int c){
if(c>idx){
cn++;
return;
}
for(int i=1;i<=n;i++){
if(gg(xh[c].x,xh[c].y,i+'0')){
a[xh[c].x][xh[c].y]=i+'0';
dfs(c+1);
a[xh[c].x][xh[c].y]='*';
}
}
}
int main(){
freopen("sm.in","r",stdin);
freopen("sm.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]=='*')idx++,xh[idx].x=i,xh[idx].y=j;
}
}
dfs(1);
cout<<cn;
return 0;
}
T2小田的mex变换
错的点
规律推错了，以后要认真思考
思路
- mex(a,b)只可能是0/1/2其余的
cout<<-1; - 如果
a==k||b==k||c==k cout<<0; - 如果
k==0那么只要一次 - 如果
k==1那如果有0就要一次，无零两次 - 如果
k==2如果有0和1一次，全0两次，其余三次
代码
#include<bits/stdc++.h>
using namespace std;
int mex(int x,int y){
for(int i=0;i<=2;i++)if(i!=x&&i!=y)return i;
}
int main(){
freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
int t;
cin>>t;
while(t--){
int a,b,c,k;
cin>>a>>b>>c>>k;
if(k==a||k==b||k==c){cout<<0<<"\n";continue;}
if(k>2){cout<<-1<<"\n";continue;}
if(k==0){
cout<<1;
}
if(k==1){
if(a==0||b==0||c==0){
cout<<1;
}
else{
cout<<2;
}
}
if(k==2){
if(a==0&&b==0&&c==0)cout<<2;
else if(a==1||b==1||c==1)cout<<2;
else cout<<3;
}
cout<<"\n";
}
return 0;
}
T3小田的绝密计划
思路
这是一个多源BFS，每搜到一个点就更新这个点的传染时间，最后输出羊王坐标的值
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,st[555][555];
int zx[10]={1,0,-1,0};
int zy[10]={0,1,0,-1};
struct P{
int x,y;
}d[100010];
void bfs(int x,int y){
queue<P>q;
q.push({x,y});
st[x][y]=0;
while(!q.empty()){
P d=q.front();
q.pop();
int xx=d.x;
int yy=d.y;
for(int i=0;i<4;i++){
int xxx=xx+zx[i];
int yyy=yy+zy[i];
if(xxx>0&&xxx<=n&&yyy>0&&yyy<=m&&st[xx][yy]+1<st[xxx][yyy]){
q.push({xxx,yyy});
st[xxx][yyy]=min(st[xx][yy]+1,st[xxx][yyy]);
}
}
}
}
int main(){
freopen("bd.in","r",stdin);
freopen("bd.out","w",stdout);
cin>>n>>m>>a>>b;
memset(st,0x3f,sizeof st);
for(int i=1;i<=a;i++){
int l,r;
cin>>l>>r;
bfs(l,r);
}
for(int i=1;i<=b;i++)cin>>d[i].x>>d[i].y;
for(int i=1;i<=b;i++)cout<<st[d[i].x][d[i].y]<<"\n";
}
T4 小田的数字游戏
没写
思路
一个数可以选和不选，选的话他周围的数都不能选，注意标记要恢复现场，最后取和的最大值
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,c,a[111][111],st[111][111];
void dfs(int x,int y,int s){
if(y>m)x++,y=1;
if(x>n){
c=max(c,s);
return;
}
if(!st[x][y]){
st[x-1][y-1]+=1;
st[x-1][y]+=1;
st[x-1][y+1]+=1;
st[x][y-1]+=1;
st[x][y+1]+=1;
st[x+1][y-1]+=1;
st[x+1][y]+=1;
st[x+1][y+1]+=1;
dfs(x,y+1,s+a[x][y]);
st[x-1][y-1]-=1;
st[x-1][y]-=1;
st[x-1][y+1]-=1;
st[x][y-1]-=1;
st[x][y+1]-=1;
st[x+1][y-1]-=1;
st[x+1][y]-=1;
st[x+1][y+1]-=1;
}
dfs(x,y+1,s);
}
signed main(){
freopen("num.in","r",stdin);
freopen("num.out","w",stdout);
int t;
cin>>t;
while(t--){
c=0;
cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
dfs(1,1,0);
cout<<c<<"\n";
}
}
T5小W走迷宫
思路
这道题是一道模版的题，只是要用到记忆化，注意记忆化的记录
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,st[1111][1111],f[1111][1111],t=0; int b[1111][1111];
int zx[10]={1,0,-1,0};
int zy[10]={0,1,0,-1};
struct P{
int x,y;
}d[100010],h[100010];
int bfs(int x,int y,int n){
queue<P>q;
int j=1;
t=0;
q.push({x,y});
b[x][y]=1;
t++;
h[t].x=x;
h[t].y=y;
while(!q.empty()){
P d=q.front();
q.pop();
int xx=d.x;
int yy=d.y;
for(int i=0;i<4;i++){
int xxx=xx+zx[i];
int yyy=yy+zy[i];
if(xxx>0&&xxx<=n&&yyy>0&&yyy<=n&&!b[xxx][yyy]){
if(st[xxx][yyy]!=st[xx][yy]){
t++;
h[t].x=xxx;
h[t].y=yyy;
q.push({xxx,yyy});
b[xxx][yyy]=1;
j++;
}
}
}
}
return j;
}
int main(){
freopen("mg.in","r",stdin);
freopen("mg.out","w",stdout);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
char d;
cin>>d;
if(d=='0')st[i][j]=0;
else st[i][j]=1;
}
}
while(m--){
int x,y;
cin>>x>>y;
if(!f[x][y]){
int j=bfs(x,y,n);
for(int i=1;i<=t;i++){
f[h[i].x][h[i].y]=j;
}
cout<<j<<"\n";
}
else {
cout<<f[x][y]<<"\n";
}
}
}