http://tjuacm.chaosheng.top/problem.php?id=1270
http://acm.hdu.edu.cn/showproblem.php?pid=2612
第一反应,对于每个KFC,分别求F和M要花的时间,加起来,每次记录最小的。
能通过样例,但WA。然后看了别的的思路,发现我这样每次都要从头算,一次bfs先把F和M 分别到所有KFC 的时间算出来,之后对每个KFC只要把相应的值加起来就行。所以直接按新思路写了,没有调下面这种方法,不知道哪里不足。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> P; const int INF = 1e8; const int N = 210; int n, m; int beginx1, beginy1, beginx2, beginy2; char matrix[N][N]; bool vis[N][N]; int row[4] = {1, 0, -1, 0}; int col[4] = {0, 1, 0, -1}; struct pos{ int x, y; int cost; }; int bfs(int beginx, int beginy, int endx, int endy){ queue<pos> q; pos f; f.x = beginx; f.y = beginy; f.cost = 0; q.push(f); vis[f.x][f.y] = true; while(q.size()){ f = q.front(); q.pop(); //满足条件 if(f.x == endx && f.y == endy){ //printf("!cost = %d\n", f.cost); return f.cost; } for(int i = 0; i < 4; i++){ pos v = f; v.x = f.x + row[i]; v.y = f.y + col[i]; if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < n && !vis[v.x][v.y] && matrix[v.x][v.y] != '#'){ vis[v.x][v.y] = true; v.cost += 11; //printf("cost = %d\n", v.cost); q.push(v); } } } } int main(){ while(cin >> n >> m){ vector<P> des; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> matrix[i][j]; if(matrix[i][j] == 'Y'){ beginx1 = i; beginy1 = j; } if(matrix[i][j] == 'M'){ beginx2 = i; beginy2 = j; } if(matrix[i][j] == '@'){ des.push_back(P(i, j)); } } } int ans = INF; for(auto d : des){ memset(vis, false, sizeof(vis)); //printf("dx = %d, dy = %d\n", d.first, d.second); int sum1 = bfs(beginx1, beginy1, d.first, d.second); memset(vis, false, sizeof(vis)); int sum2 = bfs(beginx2, beginy2, d.first, d.second); //printf("sum1 = %d, sum2 = %d\n", sum1, sum2); ans = min(ans, sum1 + sum2); } printf("%d\n", ans); } return 0; }
真的要注意细节哇!!!!!!!!!!!
WA了好多次才发现,一开始输入matrix的j应该是<m,但是写成了n!!!!所以一晚上怎么改bfs都不对,绝了QAQ
然后把第一种我原来想的也就是上面的代码改过来,不再是WA,但会超时。所以还是要用下面的写法。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; int n, m; int yx,yy,mx,my;//Y的坐标,M的坐标 char map[202][202]; int a[202][202];//保存第一个人Y到各个节点(坐标)的最小步数,有的节点不用访问,下面有说明 int b[202][202];//保存第二个人M int dx[4] = {0, 0, -1, 1}; int dy[4] = {1, -1, 0, 0}; struct pos{ int x, y; }; void bfs(int x, int y, int num[202][202]){ queue<pos> q; pos f, v; f.x = x; f.y = y; num[f.x][f.y] = 0; q.push(f); while(!q.empty()){ f = q.front(); q.pop(); for(int i = 0; i < 4; i++){ v.x = f.x + dx[i]; v.y = f.y + dy[i]; if(v.x >= 0 && v.x < n && v.y >= 0 && v.y < m && num[v.x][v.y] == 0 && map[v.x][v.y] != '#') { num[v.x][v.y] = num[f.x][f.y] + 1; q.push(v); } } } } int main(){ while(cin >> n >> m){ memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ cin >> map[i][j]; if(map[i][j] == 'Y'){ yx = i; yy = j; } else if(map[i][j] == 'M'){ mx = i; my = j; } } } bfs(yx,yy,a); bfs(mx,my,b); int ans = 1000000; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){ if(map[i][j] == '@' && b[i][j] != 0){ ans = min(ans, a[i][j] + b[i][j]);//某个KFC地点两者到达的总步数之和,取最小值。 } } cout << ans * 11 << endl; } return 0; }