Sample Input 1
3 2 4 1 0 0 1 0 0 3 2 5 1 0 0 1 0 0 4 2 5 2 0 0 2 2 0 4
Sample Output 1
Yes No Yes
Hint
第一组数据,由奶酪的剖面图可见：
第一个空洞在 ( 0 , 0 , 0 )与下表面相切；
第二个空洞在 ( 0 , 0 , 4 ) 与上表面相切；
两个空洞在 ( 0 , 0 , 2 ) 相切。
输出 Yes。
第二组数据,由奶酪的剖面图可见：
两个空洞既不相交也不相切。
输出 No。
第三组数据,由奶酪的剖面图可见：
两个空洞相交，且与上下表面相切或相交。
输出 Yes。
【数据规模与约定】
题解
建图，设0号点为起点，n+1号点为终点。将每个洞视为图中的点。若洞高度绝对值小于半径r，则起点连到该点。若洞高度大于h−r,则该点连到终点。若距离小于半径的两倍，则两个洞所代表的点连一条边。建图完成后，dfs
代码
#include<iostream> #include<cstring> #include<vector> #include<cstdio> using namespace std; typedef long long ll; vector<int> G[1005]; double ball[1005][4]; bool st[1005]; void dfs(int i){ st[i]=1; for(auto node:G[i]){ if (!st[node]) dfs(node); } } signed main(){ freopen("res.in","r",stdin); freopen("res.out","w",stdout); int t; cin>>t; while(t--){ memset(ball,0,sizeof ball); memset(st,0,sizeof st); int n; double h,r; cin>>n>>h>>r; for(int i=0;i<=n+1;i++) G[i].clear(); for(int i=1;i<=n;i++){ cin>>ball[i][1]>>ball[i][2]>>ball[i][3]; } for(int i=1;i<=n;i++){ if (ball[i][3]<=r){ G[0].push_back(i);//0号点为起点，底边 G[i].push_back(0); } if (ball[i][3]>=h-r){ G[n+1].push_back(i);//n+1号点为终点 G[i].push_back(n+1); } for(int j=i+1;j<=n;j++){ double sqrdst=(ball[i][1]-ball[j][1])*(ball[i][1]-ball[j][1]) +(ball[i][2]-ball[j][2])*(ball[i][2]-ball[j][2]) +(ball[i][3]-ball[j][3])*(ball[i][3]-ball[j][3]); if (sqrdst<=4*r*r){ G[i].push_back(j); G[j].push_back(i); } } } dfs(0); if (st[n+1]) cout<<"Yes\n"; else cout<<"No\n"; } }
机器人搬重物
Description
Output
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出−1。
Sample Input 1
9 10 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 7 2 2 7 S
Sample Output 1
12
题解
代码
#include<iostream> #include<queue> #include<cstring> #include<map> #include<iomanip> using namespace std; struct posd{ int x, y, d; }; int collidx[4] = { -1, 0,-1,0 };//障碍物 int collidy[4] = { -1,-1, 0,0 }; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int dist[55][55][4];//0 北 1南 2西 3东 map<char, int> c2i = {{'N',0},{'S',1},{'W',2},{'E',3}}; int ditu[55][55]; int n, m; bool collide(int x, int y) { if (x == 0 || y == 0 || x >= n || y >= m) return true; for (int k = 0;k < 4;k++) { int tx = x + collidx[k]; int ty = y + collidy[k]; if (ditu[tx][ty] == 1) return true; } return false; } int main() { cin >> n >> m; for (int i = 0;i < n;i++) for (int j = 0;j < m;j++) cin >> ditu[i][j]; int startx, starty, endx, endy; char startd; cin >> startx >> starty >> endx >> endy; cin >> startd; memset(dist, 0x3f3f3f3f, sizeof dist); queue<posd> q; q.push({ startx,starty,c2i[startd] }); dist[startx][starty][c2i[startd]] = 0; while (!q.empty()) { auto p= q.front(); q.pop(); if (p.d == 0 || p.d == 1) {//从南北转到东西 if (dist[p.x][p.y][2] == 0x3f3f3f3f) { dist[p.x][p.y][2] = dist[p.x][p.y][p.d] + 1; q.push({ p.x,p.y,2 }); } if (dist[p.x][p.y][3] == 0x3f3f3f3f) { dist[p.x][p.y][3] = dist[p.x][p.y][p.d] + 1; q.push({ p.x,p.y,3 }); } } if (p.d == 2 || p.d == 3) {//从东西转到南北 if (dist[p.x][p.y][0] == 0x3f3f3f3f) { dist[p.x][p.y][0] = dist[p.x][p.y][p.d] + 1; q.push({ p.x,p.y,0 }); } if (dist[p.x][p.y][1] == 0x3f3f3f3f) { dist[p.x][p.y][1] = dist[p.x][p.y][p.d] + 1; q.push({ p.x,p.y,1 }); } } //往对应方向走1/2/3步 int tx = p.x, ty = p.y; for (int _ = 0;_ <3;_++) { tx +=dx[p.d]; ty +=dy[p.d]; if (collide(tx, ty)) break; if (dist[tx][ty][p.d] != 0x3f3f3f3f) continue; dist[tx][ty][p.d] = dist[p.x][p.y][p.d] + 1; q.push({ tx,ty,p.d }); } } int res = 0x3f3f3f3f; for (int k = 0;k < 4;k++) res = min(res, dist[endx][endy][k]); if (res==0x3f3f3f3f) cout<<-1; else cout << res << endl; }
