一点点有意思的题目

1.逃离中山路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll N=1010;
ll way[N][N];
ll n,x1,y3,x2,y2;
ll dx[]={1,0,-1,0};
ll dy[]={0,1,0,-1};
ll st[N][N];
ll bfs(ll x1,ll y3,ll x2,ll y2){
    queue<pii> arr;
    arr.push({x1,y3});
    st[x1][y3]=0;
    while(!arr.empty()) {
        ll x=arr.front().first;
        ll y=arr.front().second;
        arr.pop();
        for(ll i=0;i<4;i++){
            ll a=x+dx[i];
            ll b=y+dy[i];
            if(a<1||b<1||a>n||b>n)continue;
            if(st[a][b])continue;
            if(way[a][b]==1)continue;
            st[a][b]=st[x][y]+1;
            if(a==x2&&b==y2)return st[a][b];
            arr.push({a,b});
        }
    }
}
int main(){
    cin>>n;
    string a[n+1];
    for(ll i=1;i<=n;i++)cin>>a[i]; 
    for(ll i=1;i<=n;i++){
        for(ll g=1;g<=n;g++)way[i][g]=a[i][g-1]-'0';
    }
    cin>>x1>>y3>>x2>>y2;
    cout<<bfs(x1,y3,x2,y2);
    return 0;
}

2.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
const ll N=200;
char way[N][N];
bool is[N][N];
ll dx[]={0,0,1,1,-1,-1,1,-1};
ll dy[]={1,-1,1,-1,1,-1,0,0};
void dfs(ll x,ll y){
	for(int i=0;i<8;i++){
		ll x1=x+dx[i];
		ll y1=y+dy[i];
		if(is[x1][y1])continue;
		if(x1<1||y1<1||x1>n||y1>m)continue;
		if(way[x1][y1]=='.')continue;
		is[x1][y1]=true;
		dfs(x1,y1); 
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int g=1;g<=m;g++)cin>>way[i][g];
	}
	ll sum=0;
	for(int i=1;i<=n;i++){
		for(int g=1;g<=m;g++){
			if(way[i][g]=='W'&&!is[i][g]){
				dfs(i,g);
				sum++;
			}
		}
	}
	cout<<sum;
	return 0;
}

3.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ele{
    int floor;
    int s;
};
ll n,a,b;
const ll N=300;
ll updown[N];
bool step[N];
int dfs(){
    queue<ele> q;
    q.push({a,0});
    step[a]=true;
    while(!q.empty()){
        ele cur=q.front();
        q.pop();
        if(cur.floor==b){
            return cur.s;
        }
        int up=cur.floor+updown[cur.floor];
        int down=cur.floor-updown[cur.floor];
        if(up<=n&&up>=1&&!step[up]){
            q.push({up,cur.s+1});
            step[up]=true;
        }
        if(down>=1&&down<=n&&!step[down]){
            q.push({down,cur.s+1});
            step[down]=true;
        }
    }
    return -1;
}
int main(){
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++)cin>>updown[i];
    cout<<dfs();
    return 0;
    }