# NOIP2017 普及组第三道 棋盘

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162 #include #include #include 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 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; }