think: 1廣度優先搜索+最值情況判斷 2以結構體數組為基礎的隊列思想 3反思:一開始自己用自己不成熟的枚舉思想判斷最值情況，然后一直wrong anser，調試了一下午也沒有找到問題所在，感覺有點浮躁，慢慢的穩穩地，腳踏實地，不要急于求成
sdut原題鏈接
團戰可以輸、提莫必須死 Time Limit: 1000MS Memory Limit: 65536KB
PRoblem Description 為了一些你們不知道的原因,我們把LOL的地圖抽象為一個n×m的矩陣 提莫積攢了k個蘑菇準備種到地圖上去，因為提莫的背簍漏了，所以每一個提莫走過的地方都會被擺下一個蘑菇，兩個蘑菇同時種在一個地方的話就會爆炸，所以一旦即將出現這種情況，提莫會直接傳送回家，防止自己被炸死 之前的排位賽中因為亂種蘑菇提莫已經被罵了好多次了，所以這次提莫特地查資料對當前地圖的各個位置種下蘑菇的價值做了統計，但是因為提莫行動比較笨拙，所以他每次只能移動到上下左右四個方向的格子中（如果該方向有格子的話 每次行走提莫會從四個方向挑選一個權值最大的方向，如果有最大的權值有多個，他會從這多個相同的最大權值之中找出沒有走過并且按照上下左右的優先順序挑選一個合適的方向走。如果最大權值都被走過了，他會心灰意冷的傳送回家，此時直接輸出”BOOM” （提莫會順手在他的起點順手種一個蘑菇下去
Input 多組輸入。 輸入第一行包含地圖大小n，m，蘑菇數量k。（1 <= n,m <= 100,1 <= k <= n*m) 接下來的n行每行有m個數（并且保證每個數的范圍[1,1e5) 接下來兩個整數x,y代表提莫的起點
Output 如果走到最后沒有地方可以種蘑菇了，但蘑菇還沒全部種完，輸出”BOOM”. 如果蘑菇在半途中種完了，輸出提莫所處的坐標”Teemo: x y”.
Example Input 3 3 3 1 2 3 4 5 6 7 8 9 2 2 3 3 5 1 2 3 4 5 6 7 8 9 2 2
Example Output Teemo: 3 3 BOOM
Hint
Author
以下為accepted代碼
#include <stdio.h>#include <string.h>struct node{ int x; int y; int amount;}link[10016], t, f;int map[104][104], vis[104][104];int tp, op, n, m, k;int xy[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};void Ans(int X, int Y){ link[tp].x = X; link[tp].y = Y; link[tp].amount = 1; tp++; vis[X][Y] = 1; while(op < tp) { f = link[op++]; if(f.amount == k) { printf("Teemo: %d %d/n", f.x, f.y); return; } ///vis[f.x][f.y] = 1; int Max = 0, flag = 0; for(int i = 0; i < 4; i++) { if(map[f.x+xy[i][0]][f.y+xy[i][1]] > Max) Max = map[f.x+xy[i][0]][f.y+xy[i][1]]; } for(int i = 0; i < 4; i++) { t.x = f.x + xy[i][0]; t.y = f.y + xy[i][1]; if(t.x > 0 && t.x <= n && t.y > 0 && t.y <= m && vis[t.x][t.y] == 0 && Max == map[t.x][t.y]) { flag = 1; t.amount = f.amount + 1; link[tp++] = t; vis[f.x][f.y] = 1; } } if(flag == 0) { printf("BOOM/n"); return; } } printf("BOOM/n");}int main(){ while(scanf("%d %d %d", &n, &m, &k) != EOF) { memset(map, 0, sizeof(map)); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) scanf("%d", &map[i][j]); int a, b; scanf("%d %d", &a, &b); Ans(a, b); } return 0;}/***************************************************User name: Result: AcceptedTake time: 140msTake Memory: 204KBSubmit time: 2017-02-16 18:58:27****************************************************/以下為wrong answer代碼
#include <stdio.h>#include <string.h>#define Max(a, b) (a > b? a: b)struct node{ int x; int y;}link[10000], ans;int n, m, k, x1, y1, x2, y2, tp, op, flag;int map[100][100], visit[100][100];//int jn[] = { -1, 1, 0, 0};//int jm[] = { 0, 0, -1, 1};int jn[] = {0, 0, -1, 1};int jm[] = {1, -1, 0, 0};void ANS(){ int tn1, tn2, tn3, tn4, tm1, tm2, tm3, tm4; link[tp].x = x1-1; link[tp].y = y1-1; tp++; flag++; visit[x1-1][y1-1] = 1; while(op < tp) { if(flag == k) break; ans = link[op++]; tn1 = ans.x + jn[0], tm1 = ans.y + jm[0]; tn2 = ans.x + jn[1], tm2 = ans.y + jm[1]; tn3 = ans.x + jn[2], tm3 = ans.y + jm[2]; tn4 = ans.x + jn[3], tm4 = ans.y + jm[3]; if(tn1 < 0 || tm1 < 0 || tn1 >= n || tm1 >= m) map[tn1][tm1] = -1; if(tn2 < 0 || tm2 < 0 || tn2 >= n || tm2 >= m) map[tn2][tm2] = -1; if(tn3 < 0 || tm3 < 0 || tn3 >= n || tm3 >= m) map[tn3][tm3] = -1; if(tn4 < 0 || tm4 < 0 || tn4 >= n || tm4 >= m) map[tn4][tm4] = -1; //printf("map1:%d/n", map[tn1][tm1]); //printf("map2:%d/n", map[tn2][tm2]); //printf("map3:%d/n", map[tn3][tm3]); //printf("map4:%d/n", map[tn4][tm4]); if(map[tn1][tm1] >= map[tn2][tm2] && map[tn1][tm1] >= map[tn3][tm3] && map[tn1][tm1] >= map[tn4][tm4] && visit[tn1][tm1] == 0) { //printf("tn1:%d tm1:%d/n", tn1, tm1); link[tp].x = tn1; link[tp].y = tm1; tp++; visit[tn1][tm1] = 1; flag++; if(flag == k) { x2 = tn1; y2 = tm1; break; } } else if(map[tn2][tm2] >= map[tn1][tm1] && map[tn2][tm2] >= map[tn3][tm3] && map[tn2][tm2] >= map[tn4][tm4] && visit[tn2][tm2] == 0) { //printf("tn2:%d tm2:%d/n", tn2, tm2); link[tp].x = tn2; link[tp].y = tm2; tp++; visit[tn2][tm2] = 1; flag++; if(flag == k) { x2 = tn2; y2 = tm2; break; } } else if(map[tn3][tm3] >= map[tn1][tm1] && map[tn3][tm3] >= map[tn2][tm2] && map[tn3][tm3] >= map[tn4][tm4] && visit[tn3][tm3] == 0) { //printf("tn3:%d tm3:%d/n", tn3, tm3); link[tp].x = tn3; link[tp].y = tm3; tp++; visit[tn3][tm3] = 1; flag++; if(flag == k) { x2 = tn3; y2 = tm3; break; } } else if(map[tn4][tm4] >= map[tn1][tm1] && map[tn4][tm4] >= map[tn2][tm2] && map[tn4][tm4] >= map[tn3][tm3] && visit[tn4][tm4] == 0) { //printf("tn4:%d tm4:%d/n", tn4, tm4); link[tp].x = tn4; link[tp].y = tm4; tp++; visit[tn4][tm4] = 1; flag++; if(flag == k) { x2 = tn4; y2 = tm4; break; } } //printf("map1:%d/n", map[tn1][tm1]); //printf("map2:%d/n", map[tn2][tm2]); //printf("map3:%d/n", map[tn3][tm3]); //printf("map4:%d/n", map[tn4][tm4]); //printf("visit[tn1][tm1]:%d/n", visit[tn1][tm1]); //printf("visit[tn2][tm2]:%d/n", visit[tn2][tm2]); //printf("visit[tn3][tm3]:%d/n", visit[tn3][tm3]); //printf("visit[tn4][tm4]:%d/n", visit[tn4][tm4]); } //printf("flag:%d/n", flag); if(flag == k) printf("Teemo: %d %d/n", x2+1, y2+1); else printf("BOOM/n");}int main(){ while(scanf("%d %d %d", &n, &m, &k) != EOF) { flag = 0; tp = op = 0; memset(map, 0, sizeof(map)); memset(visit, 0, sizeof(visit)); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { scanf("%d", &map[i][j]); } } scanf("%d %d", &x1, &y1); //printf("k:%d/n", k); if(k == 1) printf("Teemo: %d %d/n", x1, x2); else ANS(); } return 0;}/***************************************************User name: Result: Wrong AnswerTake time: 140msTake Memory: 196KBSubmit time: 2017-02-16 17:47:29****************************************************/新聞熱點
疑難解答
