Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
多谢前辈们,一次AC 贴上代码第一次贴代码 纪念一下 #include<iostream> #include<string.h> #include<stdio.h> #include<string> #include<queue> #define INF 999999 using namespace std; typedef class{ public: int h; int w; int step; }V; V vex[110]; int adj[110][110]; char map[60][60]; char vexid[110][110]; char visit[110][110]; int d[110]; void dfs(V start,int h,int w,int id){ queue<V> q; q.push(start); while (!q.empty()){ V vtmp1=q.front(), vtmp2; q.pop(); for (int i = 0; i < 4; i++){ vtmp2 = vtmp1; switch (i){ case 0: vtmp2.h = vtmp1.h+1; break; case 1: vtmp2.h = vtmp1.h-1; break; case 2: vtmp2.w = vtmp1.w+1; break; case 3: vtmp2.w = vtmp1.w-1; break; } if (vtmp2.h>0 && vtmp2.h<h &&vtmp2.w>0 && vtmp2.w < w&&map[vtmp2.h][vtmp2.w] != '#' && !visit[vtmp2.h][vtmp2.w]){ vtmp2.step++; visit[vtmp2.h][vtmp2.w] = 1; if (map[vtmp2.h][vtmp2.w] != ' '){ adj[id][vexid[vtmp2.h][vtmp2.w]] = vtmp2.step; } q.push(vtmp2); } } } } void prim(int vexnum){ //初始化 for (int i = 1; i < vexnum; i++){ d[i] = adj[0][i]; } d[0] = 0; int result = 0; for (int i = 1; i < vexnum; i++){ int min = INF; int vtmp = -1; for (int i = 1; i < vexnum; i++){ if (min>d[i] && d[i] != 0){ min = d[i]; vtmp = i; } } if (vtmp == -1 || min == INF){ break; } result += min; d[vtmp] = 0; //更新 for (int i = 0; i < vexnum; i++){ if (adj[i][vtmp] < d[i]){ d[i] = adj[i][vtmp]; } } } cout << result << endl; } int main(){ char c, b[100]; int N; gets(b); sscanf(b, "%d", &N); while (N--){ //各种初始化 memset(map, 0, 60 * 60); memset(vex, 0, 110 * sizeof(V)); memset(vexid, -1, 110); memset(adj, 0, 110 * 100 * sizeof(int)); //输入数据 int w, h, vexnum = 0; gets(b); sscanf(b, "%d %d", &w, &h); for (int i = 0; i < h; i++){ gets(map[i]); for (int j = 0; j < w; j++){ if (map[i][j] == 'S' ||map[i][j]=='A'){ vex[vexnum].h = i; vex[vexnum].w = j; vex[vexnum].step = 0; vexid[i][j] = vexnum; vexnum++; } } } //dfs构造图 for (int i = 0; i < vexnum; i++){ memset(visit, 0, 110 * 110); visit[vex[i].h][vex[i].w] = 1; dfs(vex[i],h,w,i); } //Prim prim(vexnum); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator