这题写的异常难受……先想着用动态规划，难受死了，才20分。然后后来再看题解，用记忆化BFS，写的也难受，主要是太难想，终于AC了。开心~
写了有6、7个钟头吧。挺羞愧的。。。我写这种题怎么能这么长时间呢……
所有测试点全部0ms。
成就感极高。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include<iostream> #include<memory.h> #include<queue> using namespace std; struct qs { //Convenient for passing parameters int tx, ty, os, rs, sc; //destination's coordinate (x,y) :tx,ty ;previous point::original status of color,real status of color :os,rs ;previous point's score:sc. qs(int tx1, int ty1, int os1, int rs1, int sc1) { tx = tx1; ty = ty1; os = os1; rs = rs1; sc = sc1; } //the init of struct }; int m, n; int arr[105][105], f[105][105]; //arr stores the color(status) of all coordinate; f stores the least gold the person will spend int shiftx[4] = { 1,-1,0,0 }, shifty[4] = { 0,0,1,-1 }; //shifts for the coordinate queue<qs> q; void execute(qs o) { //Calculate New Score //Compare Which one is smaller //Only when the new one is smaller one,will the program insert the queue int nscore = 0x7fffffff; if (o.rs != -1 && arr[o.tx][o.ty] != -1) { // C2C(R2R/Y2Y/R2Y/Y2R) {"C"："Color","2":"To","R":"Red","Y":"Yellow"}; if (o.rs == arr[o.tx][o.ty])nscore = o.sc; // R2R/Y2Y else nscore = o.sc + 1; // R2Y/T2R if (nscore < f[o.tx][o.ty] || o.tx==1&&o.ty==1) { //o.tx==1&&o.ty==1 is to create an entrance for the inital queue push f[o.tx][o.ty] = nscore; for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], arr[o.tx][o.ty], arr[o.tx][o.ty], nscore)); } } else if (o.os != -1 && arr[o.tx][o.ty] == -1) { // C2N if (o.os == 0 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Red f[o.tx][o.ty] = nscore = o.sc + 2; for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore)); nscore += 1; for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore)); } else if (o.os == 1 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Yellow f[o.tx][o.ty] = nscore = o.sc + 2; for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore)); nscore += 1; for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore)); } } } int main() { memset(arr, -1, sizeof(arr)); memset(f, 0x7f, sizeof(f)); ios::sync_with_stdio(false); cin >> m >> n; for (int i = 1; i <= n; i++) { int x, y, c; cin >> x >> y >> c; arr[x][y] = c; } f[1][1] = 0; q.push(qs(1, 1, arr[1][1], arr[1][1], 0)); while (!q.empty()) { qs cur = q.front(); q.pop(); if (cur.tx > m || cur.ty > m || cur.tx < 1 || cur.ty < 1)continue; execute(cur); } cout << (f[m][m] == 0x7f7f7f7f ? -1 : f[m][m]) << endl; } |