杂题训练 2020.7.3

迷宫
https://www.luogu.com.cn/problem/P1605

#include <bits/stdc++.h>
using namespace std;
const int N=10;
int g[N][N],v[N][N],sx,sy,gx,gy,d[N][N],ans,zz[N][N];
int n,m,t;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
void walk(int x,int y){
    if(x==gx&&y==gy){
        ans++;
        return;
    }
    else{
        for(int k=0;k<4;k++){
            int nx=x+dx[k];
            int ny=y+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&!v[nx][ny]&&!zz[nx][ny]){
                v[x][y]=1;
                walk(nx,ny);
                v[x][y]=0;
            }
        }
    }
}
int main(){
    cin>>n>>m>>t;
    cin>>sx>>sy>>gx>>gy;
    for(int p=0;p<t;p++){
        int i,j;
        cin>>i>>j;
        zz[i][j]=1;
    }
    walk(sx,sy);
    cout<<ans;
    return 0;
}

填涂颜色
https://www.luogu.com.cn/problem/P1162

#include <bits/stdc++.h>
using namespace std;
const int N=50;
int n;
int g[N][N],col[N][N];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
void dfs(int x,int y){
    if(x<0|x>n+1||y<0||y>n+1||col[x][y]) return;
    col[x][y]=1;
    for(int k=0;k<4;k++)dfs(x+dx[k],y+dy[k]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
            if(g[i][j]==0) col[i][j]=0;
            else col[i][j]=2;
        }
    }
    dfs(0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(col[i][j]==0) cout<<2<<" ";
            else cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

[USACO10OCT]Lake Counting S
https://www.luogu.com.cn/problem/P1596

#include <bits/stdc++.h>
using namespace std;
const int N=150;
int n,m,cnt;
int dx[8]={0,1,1,1,0,-1,-1,-1},dy[8]={1,1,0,-1,-1,-1,0,1};
char g[N][N];
void dfs(int x,int y){
    if(g[x][y]=='W') g[x][y]='.';
    for(int k=0;k<8;k++){
        int nx=x+dx[k];
        int ny=y+dy[k];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&g[nx][ny]=='W')dfs(nx,ny);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='W'){
                dfs(i,j);
                cnt++;
            }
        }
    }
    cout<<cnt;
    return 0;
}

[COCI2008-2009#2] PERKET
https://www.luogu.com.cn/problem/P2036

#include <bits/stdc++.h>
using namespace std;
const int N=15;
int a[N],b[N],ans=0x7f7f7f,n;
void dfs(int now,int s,int t){
    if(now>n){
        if(s==1&&t==0) return;
        else{
            ans=min(ans,abs(s-t));
            return;
        }
    }
    dfs(now+1,s*a[now],t+b[now]);
    dfs(now+1,s,t);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    dfs(1,1,0);
    cout<<ans;
    return 0;
}

[USACO08FEB]Meteor Shower S
https://www.luogu.com.cn/problem/P2895

#include <bits/stdc++.h>
using namespace std;
int c[310][310];//有没有被访问
int t[310][310];//流星造访的最早时间
int m;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
struct place{
    int x,y,time;
}p;
int main(){
    cin>>m;
    for(int i=0;i<=305;i++){
        for(int j=0;j<=305;j++)
            t[i][j]=-1;
    }
    for(int i=1;i<=m;i++){
        int x,y,ti;
        cin>>x>>y>>ti;
        if(ti<t[x][y]||t[x][y]==-1) t[x][y]=ti;
        for(int k=0;k<4;k++){
            int nx=x+dx[k];
            int ny=y+dy[k];
            if(nx>=0&&ny>=0&&(t[nx][ny]==-1||ti<t[nx][ny]))t[nx][ny]=ti;
        }
    }
    queue<place> q;
    p.x=0,p.y=0,p.time=0;
    c[0][0]=1;
    q.push(p);
    while(q.size()){
        place now=q.front();
    //    cout<<now.x<<" "<<now.y<<" "<<now.time<<endl;
        q.pop();
        for(int k=0;k<4;k++){
            int nx=now.x+dx[k];
            int ny=now.y+dy[k];
            if(nx>=0&&ny>=0&&!(c[nx][ny])&&(t[nx][ny]==-1||now.time+1<t[nx][ny])){
                if(t[nx][ny]==-1)
                {
                    cout<<now.time+1<<endl;
                    return 0;
                }
                place New;
                New.x=nx;
                New.y=ny;
                New.time=now.time+1;
                c[nx][ny]=1;
                q.push(New);
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}